aspose file tools*
The moose likes Java in General and the fly likes Binary Tree  remove node algorithms Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Binary Tree  remove node algorithms" Watch "Binary Tree  remove node algorithms" New topic
Author

Binary Tree remove node algorithms

KR Campbell
Ranch Hand

Joined: Mar 26, 2004
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

Joined: Jun 02, 2003
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.


http://home.arcor.de/hirnstrom/bewerbung
KR Campbell
Ranch Hand

Joined: Mar 26, 2004
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

Joined: Mar 26, 2004
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

Joined: Mar 26, 2004
Posts: 124
Oh.. that's what you were saying.
Thanks.
Ken
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Binary Tree remove node algorithms