Binary tree remove method

Question

I am doing some extra work in my computer science class trying to get better at understanding the logic of data structures. Specifically, I am trying to write a remove function for a sorted binary tree:

private boolean remove(Node cRoot, Object o) {
  if (cRoot == null) {
    return false;
  }
  else if (cRoot.item.equals(o)) { 
    //erase node fix tree
    return true;
  }
  else if (((Comparable)item).compareTo(cRoot.item)<=0){
    return remove(cRoot.lChild, o);
  }
  else { 
     return remove(cRoot.rChild,o);
  }
}

I am unsure how to go about writing the "erase node fix tree" part of the code. Mainly how many cases are there and how do I tackle them?

Answer 1

The basic pseudo-code for erasing a node from a sorted tree is pretty simple:

1. erase the node value
2. find child node with maximum value
3. make it the root node
4. if it had children - goto 2 recursively

Basically what you are doing is bubbling nodes up the tree, each time the maximum of the children node in each node, so that in the end you stay with a sorted tree, and only one node missing at the end of the full path you went.

Also - see wikipedia on the subject, they have some sample code in C as well.

Answer 2

There are generally two ways of performing a remove on the tree:

First method:

Remove the node, then replace it with either child. Then, resort the tree by doing parent-child swapping until the tree is once again sorted.

The second method:

Traverse the tree to find the next (highest or lowest) value that belongs as the root*, if it is a leaf node, swap that with the root, then trim off the value you want to remove. If it is an internal node, you will have to recursively call remove on that node. Repeat until a leaf node is removed.

*What I mean is, if you convert your BST into a sorted list, then you will want to pick either value to the left or right of the root as the new root. I.e. leftmost child of the right subtree, or right most child of the left subtree.

Answer 3

In the simple case3 you can use next algorithm:

if(removed node had left child)
{
   place left child instead of removed node;
   most_right = most right leaf in the left subtree;
   move right child of removed node as right child of most_right;
}
else
{
   place right child instead of removed node
}

In more complicated case you may need to rebalance your tree (see AVL trees, http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html for C++ example)

Answer 4

//leaf-delete node //1-child Promote the subtree //2-child case replace the node with either //in order successor or predecessor //left most of the right subtree or //right most of the left subtree