• Post Reply Bookmark Topic Watch Topic
  • New Topic

Difference between Binary search tree and polymorhic BST ?  RSS feed

 
John Laker
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am trying to grasp the difference between a BST and a polymorphic BST. I have a fairly good understanding about BST, but haven't been able to find much on PBST on google.
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24217
38
Chrome Eclipse IDE Mac OS X
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As I understand the term, it's just an implementation detail, really, and not worthy IMHO of a separate name.

In many traditional BST implementations, you use a "null" child to represent an empty subtree. So if my Node class has two members "left" and "right", then my "find()" method has to check whether "left" is null first before recursively calling left.find(), and so on.

In a "polymorphic BST", you don't use null to represent an empty subtree, you use a polymorphic variant of Node called, for example, EmptyNode. (In other words, both Node and Empty node implement the same interface, and all the code in Node assumes the children are instances of that interface.) So you don't have to check for null before calling find() on a child -- you just call it, and the version in EmptyNode just does nothing.

So if you think eliminating a few null checks is worth an interface and an extra class, then PBST is a good idea!
 
John Laker
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ernest Friedman-Hill wrote:As I understand the term, it's just an implementation detail, really, and not worthy IMHO of a separate name.

In many traditional BST implementations, you use a "null" child to represent an empty subtree. So if my Node class has two members "left" and "right", then my "find()" method has to check whether "left" is null first before recursively calling left.find(), and so on.

In a "polymorphic BST", you don't use null to represent an empty subtree, you use a polymorphic variant of Node called, for example, EmptyNode. (In other words, both Node and Empty node implement the same interface, and all the code in Node assumes the children are instances of that interface.) So you don't have to check for null before calling find() on a child -- you just call it, and the version in EmptyNode just does nothing.

So if you think eliminating a few null checks is worth an interface and an extra class, then PBST is a good idea!


unfortunately my project requires me to implement PBST. Could you please demonstrate with code how PBST works.
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24217
38
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, it sounds like implementing the tree is your project, so I don't want to give too much away. If you try implementing what I described, you can post here when you get stuck and folks will be happy to help you along from that point.
 
John Laker
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ernest Friedman-Hill wrote:Well, it sounds like implementing the tree is your project, so I don't want to give too much away. If you try implementing what I described, you can post here when you get stuck and folks will be happy to help you along from that point.


here goes then.

I'm trying to implement size method for NonEmptyTree and here is the code I have.



I think I have the else part right with it returning recursively the size of the left and right children. I'm not sure if the if part is correct.
 
Campbell Ritchie
Marshal
Posts: 56599
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't understand what that method is supposed to do, so I can't comment about whether the bit about == 0 return 0 is correct.
 
Wouter Oet
Bartender
Posts: 2700
IntelliJ IDE Opera
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is to advanced for Beginning Java so I've moved it to Java In General.
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24217
38
Chrome Eclipse IDE Mac OS X
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
J Laker wrote:
I think I have the else part right with it returning recursively the size of the left and right children. I'm not sure if the if part is correct.


OK, this is a good place to start. So in this method, you're comparing "key" to "this.key", although there's no parameter named "key". Therefore "key" and "this.key" are both going to refer to the same thing, the instance variable named "key". The comparison will always be true, and we'll always return 0.

To put this one on the right track: I don't think "size" depends on the key at all. The size of a NonEmptyTree will always be 1 plus the size of the left subtree plus the size of the right subtree. The size of an EmptyTree, on the other hand, will always be 0; if a NonEmptyTree has an EmptyTree child, then one of those subtree sizes will be 0.

So the size() method should actually be much simpler than this -- no "if" is needed.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!