Binary Search Trees

Binary search trees (BST) are binary trees where values are placed in a way that supports efficient ( $O(log n)$) searching. In a BST, all values in the left subtree value in current node < all values in the right subtree. This rule must hold for EVERY subtree, ie every subtree must be a binary search tree if the whole tree is to be a binary tree. The following is a binary search tree:

The following is NOT a binary search tree:

A binary search tree allows us to quickly perform a search on a linking structure (under certain conditions). To find a value, we simply start at the root and look at the value. If our key is less than the value, search left subtree. If key is greater than value search right subtree. It provides a way for us to do a "binary search" on a linked structure which is not possible with a linear linked list. Note that we will never have to search the subtrees we eliminate in the search process... thus at worst, searching for a value in a binary search tree is equivalent to going through all the nodes from the root to the furthest leaf in the tree.

TNode<TYPE>* BST::Search(TYPE key){
  TNode* retval=NULL;
  TNode* curr=root_;
  while(retval && curr){
    if(curr->data==key)
      retval=curr;
    else if(key < curr->data)
      curr=curr->left_;
    else
      curr=curr->right_;
  }
  return retval;
}