BACK

Binary Search Tree Overview

NEXT

PowerPoint Presentations:    Sahni's Lecture 20      Sahni's Lecture 21     Locally maintained slide set

In addition to the Binary Expression Tree, we can use binary trees to store all kinds of objects.  One such tree is called the Binary Search Tree (BST).  In this class we will do only a brief introduction, and then the topic will be massively expanded in CScD-320, Algorithms (formerly CScD-327, Data Structures II).

We will only cover the BST for insertion and node finding.

/**
 * Binary search tree node
 *    data area
 *    left  link  --- left subtree
 *    right link  --- right subtree
 */
private static class BSTnode
{  Comparable data;  // I.e., there MUST be an ordering
// If equal keys are allowed, choose which way to go on "equals"
   BSTnode    left,  // "<" subtree.
              right; // ">" subtree.

   BSTnode ( Comparable data ) // Construction only of leaf nodes.
   {  this.data = data;
      this.left = this.right = null;
   }
} // end class BSTnode

If a binary tree were built upon simple Objects, finding the Object that tests as equal to a given Object would potentially require traversal of the entire binary tree.

public Object find ( Object value )
{  BSTnode node = find(root, value);
   return  node == null ? null : node.data;
}

BSTnode find ( BSTnode node, Object value )
{  BSTnode found = node;

// Node exists, but it is not the correct one.  NOTE:  it is critical that
// the base class "equals" of Object be overridden as appropriate.
   if ( node != null && !value.equals(node.data) )
   {
      found = find ( node.left, value );   // Search left first
      if ( found == null )                 // Failed to find on left
         found = find( node.right, value );// so search right
   }

   return found;
}

In the Binary Search Tree, however, we have Comparable Objects, so that we can take advantage of ordering information.  We can build a tree that acts like the Binary Search within an array.  The recursive search similar to the above unordered search only needs to traverse one child at any node.

BSTnode find ( BSTnode node, Comparable value )
{
   if ( node == null )                      // Failed to find
      return node;                          // Base case 1
   else if ( value.compareTo(node.data)<0 ) // Down left
      return find ( node.left, value );
   else if ( value.compareTo(node.data)>0 ) // Down right
      return find ( node.right, value );
   else                                     // We GOT it!
      return node;                          // Base case 2
}

That means, however, that there is only one path to be traversed in searching for the Comparable object.  In addition, examining the above code segment shows that it is a perfect example of tail recursion — each recursive call is the very last operation in the execution of the method.  That means that the recursive call can be replaced with a parameter update.

BSTnode find ( BSTnode node, Comparable value )
{
   while ( node != null )                   // Continue to failure
   {
      if (value.compareTo(node.data)<0)     // Down left
         node = node.left;
      else if (value.compareTo(node.data)>0)// Down right
         node = node.right;
      else                                  // We GOT it!
         break;                             // so exit loop
   }

   return node;
}

Hand-out on finding items in trees   TreeFind.rtf

Building the Binary Search Tree

Try to find the item.  The point at which you fail to find it is exactly where it belongs.  Note:  the following implementation allows equal key values and inserts them to the right.  If equal key values are not allowed, the bare else would become else if (value.compareTo(node.data)>0)  Then the bare else would be followed by duplication error code.

/**
 * Insert a value in the BST.
 */
/* Iterative implementation:   */
   public void insert(Comparable value)
   {  insert(root, value);  }

// NOTE:  This implementation is allowing equal keys.
   void insert(BSTnode node, Comparable value)
   {  if ( node == null )
         root = new BSTnode (value);
      else
      {  while(true)  // breaks on node creation
         {
            if ( value.compareTo(node.data) < 0 )
               if ( node.left != null )
                  node = node.left;
               else
               {  node.left = new BSTnode (value);
                  break;
               }
            else   // On equals, we will insert to the right.
               if ( node.right != null )
                  node = node.right;
               else
               {  node.right = new BSTnode (value);
                  break;
               }
         }
      } // end if/else
   } // end insert()

/**
 * Insert a value in the BST.
 */
/* Recursive implementation:   */
   public void insert (Comparable value)
   {  root = insert ( value, root );  }

// NOTE:  This implementation is allowing equal keys.
   private BSTnode insert ( Comparable value, BSTnode node )
   {
      if ( node == null )
         return new BSTnode(value);
      else if (value.compareTo(node.data) < 0)
         node.left  = insert ( value, node.left );
      else
         node.right = insert ( value, node.right );
      return node;
   }

Other Tree Methods

Emptying the binary search tree is simply a matter of setting the root to null — the Java garbage collector will then recover all the nodes.
public void clear()
{  root = null;  }   // Garbage collector sweeps up afterwards

(Sub)Tree Size:  This is handled recursively:  the empty tree (null) has zero nodes, otherwise the tree has all the nodes in its left subtree plus all the nodes in its right subtree plus itself:

public int size()
{  return size(root);  }

private int size(BSTnode current)
{  return current == null ? 0
                          : size(current.left)+size(current.right)+1;
} // end size()

Node Height:  This is also handled recursively.  a leaf node is defined to have a height of zero, so that the empty tree (null) has a height of -1.  A non-leaf node has the height one more than the larger of its two child nodes — this gives us the number of links in the path from this node down to its farthest leaf node.  Alternatively, it is the number of levels (starting from the root as level zero) in the subtree with this node as its root.

public int height()
{  return height(root);  }

private int height(BSTnode current)
{  if (current == null)
      return -1;
   else
      return Math.max(height(current.left),height(current.right))+1;
} // end height()

Tree Traversal:  the in-order traversal of the binary search tree will process the nodes in strict order.  If the in-order traversal goes left first, the nodes will be process from smallest to largest.  If, however, the traversal goes right first, the nodes will be processed from largest to smallest.  To visually display the tree, we can use indentation to show the tree levels, and we can also process largest to smallest, so that rotating the display by 90o clockwise we see the entire tree with its levels.

/**
 * Walk through the tree; display is to be non-ascending order.
 * The display uses indentation to show placement of values within
 * the binary search tree.
 */
public void walk()
{  if (root == null)      // Print a diagnostic on an empty tree
      System.out.println ("Empty tree.");
   else                   // Otherwise show the non-empty tree
      inOrder(root, "");  // WOULD work for an empty tree
} // end walk()

// To get non-ascending order, do an in-order traversal of the tree
// processing right subtrees first.
void inOrder(BSTnode item, String prefix)
{
   if ( item == null) return;            // I.e., empty tree
   // Note that each call increases the indentation prefix
   inOrder(item.right, prefix+"  ");     // Process Right sub-tree
   System.out.println (prefix + item.data);
   inOrder(item.left, prefix+"  ");      // Process Left sub-tree
} // end inOrder()

BSTsmp.rtf       Hand-out with the simple BST implementation  [see below to access through .txt files]
BSTsmp.exe     Directly executable copy (exe wrapper around a jar file)


Java code files

BSTsmp.java       Code for this simple implementation [.txt]
BSTexercise.java  Code to exercise it  [.txt]
BSTsmp.jar        Executable jar file:  "java -jar BSTsmp.jar"
BSTsmp.exe        Above jar file in an exe wrapper
SampleRun.txt     Sample run using the title of our text book