• 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Binary Tree remove node algorithms

 
Ranch Hand
Posts: 124
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,
I'm playing around with binary trees at the minute and having one of those periods where I am wondering whether I have been lobotomised in my sleep. I'm trying to think of algorithms for removing an element from a binary tree. At the minute all I can come up with is this:
Case: node is an internal node.
1. Search for the node ( left subtree < value, right subtree > value)
2. (if !=null) Connect the right subtree of node to node's parent in place of node.
3. Keep a reference, temp, to the left subtree of node.right and reconnect
the left subtree of node as the left subtree of node.right.
4. Add() each of the nodes in temp to node.right.
5. node=null.
Does anyone know of a more efficient general algorithm?
Regards,
Kenny
 
Ranch Hand
Posts: 1923
Scala Postgres Database Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I didn't do much about trees, but couldn't you just:
3. Find the leftmost node in the old_right_subtree=new subtree.
4. Connect the removed left_subtree to this node (left).
since the order in the left subtree isn't changed, it needn't be added node by node I guess.
 
KR Campbell
Ranch Hand
Posts: 124
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,

Thanks, but I think the problem with that is that the removed node has a left subtree and the right node that is moving up to replace it also has a left subtree. They need to be merged somehow.
For example:

Regards,
Ken
 
KR Campbell
Ranch Hand
Posts: 124
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,

Thanks, but I think the problem with that is that the removed node has a left subtree and the right node that is moving up to replace it also has a left subtree. They need to be merged somehow.
For example:
15
/ \
9 23
/ \ / \
6 12 22 24
/ \ / \
1 7 11 14
Supposing I want to remove node with value 9. If I move 12 up to replace it
what do I do with 11? In fact, looking at this I just realised that I have to do it the other way round. Its 9's left subtree that needs to be added to 11 to keep the order.
I still feel that I'm missing something.


Regards,
Ken
 
KR Campbell
Ranch Hand
Posts: 124
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Oh.. that's what you were saying.
Thanks.
Ken
 
Gravity is a harsh mistress. But this tiny ad is pretty easy to deal with:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic