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