Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Binary Tree remove node algorithms

KR Campbell
Ranch Hand
Posts: 124
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

Stefan Wagner
Ranch Hand
Posts: 1923
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
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
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
Oh.. that's what you were saying.
Thanks.
Ken