*** Binary Search Tree ***
--------------------------

Files:  bst.c, bst.h

Each node in a binary search tree has the following fields:
 - a key.  (the source files bst.c and bst.h do not have a key field for tree
            nodes, since the key is obtained from the item a node points to.)
 - a pointer to the item it represents.
 - left and right child pointers.
Consider a node, x, in a binary search tree.  The keys of nodes in the tree
satisfy the following properties:
 - If node x has a left child node, l, then key(l) < key(x).
 - If node x has a right child node, r, then key(r) > key(x).
      (or key(r) >= key(x) if the uniqueness of keys is not enforced.)
The shape of a binary search tree depends on how the keys are inserted into the
tree.  The main operations on a binary search tree are described below.  This
describes each operation but does not describe the details of how each
operation is implemented in the source file bst.c.  For details, refer to the
files bst.c and bst.h.

insert()
--------
Consider inserting an item, i, with a key, k, into the binary search tree.  A
new node, x, is created with its key set to k, item pointer set to i, and left
and right child pointers set to NULL.  If the tree root is empty then x is
inserted as the root of the tree.  Otherwise, starting at the root of the tree,
the tree is searched as follows until an empty position is located.
Let the p point to the current position of the search.
 - If the position pointed to by p is empty, then insert x at p.
   Otherwise:
    - If key(x) < key(p), then update p to p->left, else update p to p->right.

find()
------
Consider searching the tree for the node corresponding to an item, i, with key,
k.  If the root position is empty then there are no nodes in the tree, and
"not found" is returned.  Otherwise the tree is searched as follows.
Let p point to the current position of the search.
 - If the position pointed to by p is empty then "not found" is returned.
 - If k == p->key, then found, so stop searching.
   Otherwise:
    - if k < p->key, then update p to p->left, else update p to p->right.
The search terminates with p pointing to the first node that matches key k.

find_min()
----------
Consider searching the tree for the node with the smallest key.  If the root
position is empty then there are no nodes in the tree, and "not found" is
returned.  Otherwise the tree is searched as follows.  Let p point to the
current position of the search.
 - While p->left is not empty update p to p->left;
The search terminates with p pointing to the left-most node, that is, the node
with the smallest key.

delete()
--------
To delete the node corresponding to an item, i, with key, k, find() is first
used to locate the node.  Let the node that is found be called p.  To delete
node p from the tree, the tree needs to be rearranged.  Rearrangement involves
child trees of node p.  Call the parent of node p, prev_p.
 - If one of the children of node p is missing, then the other child can
   replace node p as a child of prev_p.
 - Otherwise, if both the left and right children of node p exist, then the
   minimum node, m, in the right sub-tree of node p is used for replacing p.
   Denote the parent of node m as prev_m.
    - If prev_m != p, then m is removed to replace p, and the right child of m
      replaces m as a child of prev_m.
    - Otherwise no removal of m is necessary since m can be moved up to
      replace p.

Some examples of the delete() cases shown below.

Right child missing:                     Left child missing:

         O prev_p        O prev_p            O prev_p          O prev_p
        / \             / \                 / \               / \
       /               /                   /                 /
      O p       --->  O c                 O p        --->   O c
     /               / \                   \               / \
    /                                       \
   O c                                       O c
  / \                                       / \


Both children, and prev_m != p:

            O prev_p                O prev_p   
           /                       /
          /                       /
         O p                     O m
        / \                     / \
       /   \                   /   \
      O     O                 O     O
     / \   / \       --->    / \   / \
         ...                     ...
         /                       /
        O prev_m                O prev_m
       / \                     / \
      /                       /
     O m                     O child_m
      \                     / \
       \
        O child_m
       / \


Both children, and prev_m = p:

            O prev_p                O prev_p   
           /                       /
          /                       /
         O p  prev_m             O m
        / \                     / \
       /   \                   /
      O     O m               O  
     / \     \       --->    / \


delete_min()
------------
This uses the same process as find_min(), to locate the minimum node.  Let the
minimum node be p.  Then p has no left child, so the right child of p can be
moved up to replace p.