• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Devaka Cooray
  • Knute Snortum
  • Paul Clapham
  • Tim Cooke
Sheriffs:
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Bear Bibeault
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Ron McLeod
  • Piet Souris
  • Frits Walraven
Bartenders:
  • Ganesh Patekar
  • Tim Holloway
  • salvin francis

Binary Trees Delete Method HELP!!!!  RSS feed

 
Ranch Hand
Posts: 60
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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) {

 
Marshal
Posts: 64493
225
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Posts: 64493
225
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 60
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Posts: 60
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!