wood burning stoves 2.0*
The moose likes Beginning Java and the fly likes Binary Trees Delete Method HELP!!!! Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Binary Trees Delete Method HELP!!!!" Watch "Binary Trees Delete Method HELP!!!!" New topic
Author

Binary Trees Delete Method HELP!!!!

Tarrell Fletcher
Ranch Hand

Joined: Oct 07, 2011
Posts: 60
Ok..I've been at this for hours and I can't figure it out. Before you all say right it down I already did that and such I just can't seem to find out how to completely remove the tree. I cannot use any null references which is why this is so hard to do because it has to be straight recursion. Here is my code I have so far:public Tree<K, V> delete(K key) {

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39044
    
  23
And you never will figure it out on screen.
One suggestion: dump the entire contents of the tree into a List, delete one element and then repopulate the tree. Remember not to repopulate a tree from an ordered List in order, otherwise it degenerates to a singly‑linked list. Repopulate it with the middle element (½‑way point) first, then the elements at each ¼, then at each ⅛, etc. Then you will get some approximation of a balanced tree.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39044
    
  23
Another suggestion:
Write down the structure of your tree with some likely values attached to each node. Remember there are bound to be nulls all over the place. You should now have a little diagram.
Remove one of the nodes. Start with a leaf and see how that alters the structure of the tree. Then remove a non‑leaf node and see how the tree alters. Convert the changes on the diagram into instructions for how to remove a node, and then convert that lot to code.
Tarrell Fletcher
Ranch Hand

Joined: Oct 07, 2011
Posts: 60
Campbell Ritchie wrote:Another suggestion:
Write down the structure of your tree with some likely values attached to each node. Remember there are bound to be nulls all over the place. You should now have a little diagram.
Remove one of the nodes. Start with a leaf and see how that alters the structure of the tree. Then remove a non‑leaf node and see how the tree alters. Convert the changes on the diagram into instructions for how to remove a node, and then convert that lot to code.


That's just it, I can't make any references to null values like if(such == null). I can't make a new tree and reinsert the values back into the tree in the delete method. This is why its bugging me, I already drew it up on paper a long time ago to see how I was gonna do it. The problem I am having is removing that leaf/tree. I can switch the key that needs to be removed with the left max or right min but when the method ends and I print the tree that left is now on the map twice. Its on there twice because its in the spot that needed to be removed which is fine, and its still in its original place. Like is there some type of command that deletes the tree leaf.?
Tarrell Fletcher
Ranch Hand

Joined: Oct 07, 2011
Posts: 60
Let me break down my approach. I'm trying to bubble my way through, my method first finds the tree/node with the attached key. I then set that tree with the right min key and if its no key there I then retrieve the left max. Next depending on which worked I then redo the delete method either right or left by now passing in the max or min key. Basically the program should replace..redo...replace..redo...til it gets to the bottom then delete the tree/node. I tried it on a tree with keys 10 , 5 , 12, 2, 6 but it removes the 10, but then I have two 12 values.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Binary Trees Delete Method HELP!!!!