From PBDN

Binary Search Trees

Applet

Arsen Gogeshvili has an excellent Binary Search Tree Applet.

The interface is pretty intuitive. Note that you have to turn off AVL support (enabled by default) if you want to play with vanilla BSTs.

Also note that it uses the predecessor rather than the successor (used on p.262) when deleting nodes.

Delete Algorithm

The TREE-DELETE algorithm (p.262) is not a picture of clarity. Frankly, I think it's very poor indeed and serves to confuse rather than illuminate. I think the following version is much clearer.

Outline

• If the node as no children, it is simply dropped.
• If the node has exactly one child, it is bypassed and it's sole child is connected to its parent.
• If the node has two children, then its successor (or predecessor) is copied to its current position and the old successor (or predecessor) is dropped (if a leaf) or bypassed (if it has a child)

For the last step, remember that the successor or predecessor, by definition, cannot have more than one child.

The following version of the algorithm is exactly equivalent both to the above and to the version in the book (p.262), but consolidates the "drop or bypass" into one place, a bit like the book version. I'm using a hash (#) as the comment symbol and have put explicit ends in for blocks.

TREE-DELETE(T,n)
   if left(n) ≠ NIL and right(n) ≠ NIL, then
      # The node to be deleted has two children
      d ← TREE-SUCCESSOR(T,n)          # It's OK to use the predecessor here too
      data(n) ← data(d)                # Copy data from the successor into n's position
   else
      # The node to be deleted has at most one child
      d ← n
   end # if ...
   
   # At this point, 'd' has at most one child: it is either the successor (having at most
   # one child) of n, if n has two children, or n itself, if n has zero or one child. 

   if left(d) = NIL and right(d) = NIL, then
      # Node 'd' has no children
      NODE-DROP(T,d)
   else
      # Node 'd' has exactly one child
      NODE-BYPASS(T,d)
   end # if ...

   return d
end # TREE-DELETE

NODE-DROP() is only ever called on nodes with no children. If we're dropping the root node, then we're effectively deleting the tree, otherwise, we have to set the left or right child pointer in the parent, which links to the node to be dropped, to NIL, signifying absence of that child.

# For nodes with no children:
NODE-DROP(T,n)
   if parent(n) = NIL
      # We've been asked to drop a root node with no children
      T ← NIL
   else
      if n = left(parent(n)), then
         left(parent(n) ← NIL
      else
         right(parent(n)) ← NIL
      end # if
   end # if
end # NODE-DROP

NODE-BYPASS() is only called on nodes with exactly one child node. First we determine whether the child is the left node or the right node, then we determine whether the the node to be bypassed is its parent's left or right child, then bypass the node by connecting the child to be the left or right child of the parent as appropriate.

# For nodes with exactly one child
NODE-BYPASS(T, n)
   if right(n) = NIL
      c ← left(n)
   else
      c ← right(n)
   end # if

   if parent(n) = NIL
      # We've been asked to bypass a root node with one child
      root(T) ← c
   else
      if n = left(parent(n))
         left(parent(n)) ← c
      else
         right(parent(n) ← c
      end # if
   end # if
end # NODE-BYPASS 

Back to Datastructures main page.