Databases
StackOverflow2013
Postsdbo
POPolymorphic Binary Search Tree without null as "empty node"
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POPolymorphic Binary Search Tree without null as "empty node"
    primarykey
    data
    text
    <p>I am working on a school project where we have to implement a polymorphic binary search tree that instead of using null references to "empty" parts of the tree, uses two classes (NonEmptyTree and EmptyTree) that you are supposed to use polymorphism to work out when certain actions should take place.</p> <p>For example, if I want to insert a particular key value in a non-polymorphic Binary Search Tree, typically you could just recursively compare against null as you move through your tree, sticking in your value whenever you get a compareTo value of 0. However in this case, because of the design of this EmptyTree class (there is only one instance of it), you are essentially forbidden from actively comparing against "EmptyTree.getInstance()" which "frees up" the single instance of EmptyTree. (getInstance() is a static method). </p> <p>I am attaching a link to the two classes with the code I have written so far. I think Pastebin's syntax highlighting is much easier to read than inserting all my code in here, so hopefully this is OK. </p> <p>I am not looking for solutions or any major giveaways, but I am extremely frustrated because it seems illogical to implement the tree this way. (I have already implemented a fairly complete BST with null references, but it seems this exercise was pointless as I have no idea how to move forward). In addition, this is not due until next Sunday so my anger is not at all the result of procrastination but rather intellectual frustration at my sense of personal inadequacy.</p> <p>Any insight is appreciated.</p> <p>The NonEmptyTree class: <a href="http://pastebin.com/" rel="nofollow">http://pastebin.com/</a></p> <p>The EmptyTree class: <a href="http://pastebin.com/" rel="nofollow">http://pastebin.com/</a></p> <p>As you can see, I make extensive use of the EmptyTree.getInstance() method as it seems like a more or less efficient way to check whether or not I should instantiate a new NonEmptyList to stick in that place. However, the Professor's words in the project specification specifically state: "You are expected to use polymorphism (and exception handling, where appropriate) to handle the differences between empty and nonempty trees. Failure to do so will result in a large negative adjustment to your project grade."</p> <p>However, I feel like these instructions contradict his lectures last semester where the message was "never ever EVER use exception handling for "control-flow", i.e. misusing catching exceptions as a way to control the behavior of the code." Even the single method that I wrote which uses a try-catch block to return a Tree feels like blasphemy.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USArthur Collé
    1. USArthur Collé
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POPolymorphic Binary Search Tree without null as "empty node"
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI understand your frustration. But remember that it can be difficult to write questions about specific parts of the Java language without it all feeling a bit pointless. You are correct about not using exceptions to control program flow - I'm wondering if that is what the professor is really looking for, or whether his question is badly worded. Maybe clarify that next time you meet? You'll get brownie points for talking about his earlier lectures :-)
      singulars
      1. POPolymorphic Binary Search Tree without null as "empty node"
      1. USDuncan Jones
    2. COHey I have been coding for 7 hours straight. I figured it all out. Basically, just as Samuel said, the point of the entire exercise is to declare most variables as type "Tree<K,V>", and then because we have two inherited classes (EmptyTree<K,V> and NonEmptyTree<K,V>), we can simply specify in one of the classes methods the types of behaviors we want to have occur. So for example, we can recursively call an "insert" method and throughout the entire time that "NonEmptyList"'s are passed in, the compareTo method checks the keys in order to stick it in the right spot, and then when an EmptyList
      singulars
      1. POPolymorphic Binary Search Tree without null as "empty node"
      1. USArthur Collé
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload