4.3 Binary search tree

Binary search tree

1. binary search tree property (bstp)

Consider the following binary tree of Integer objects.

Notice the following property:

• all elements in the left subtree are less than the root element,
• and the root element is less than all elements in the right subtree.

Moreover, this property holds recursively for all subtrees.  It is called the binary search tree (BST) property.  

In general, instead of Integer objects, suppose we have a set of objects that can be compared for equality with "equal to" and "totally ordered" with an order relation called "less or equal to" .  Define "less than" to mean "less or equal to" AND "not equal to".  Let T be a BiTree structure that stores such totally ordered objects.  

Definition of binary search tree property

The binary search tree property (BSTP) is defined on the binary tree structure as follows.

• An empty binary tree satisfies the BSTP.
• A non-empty binary tree T satisfies the BSTP if and only if 
  • the left and right subtrees of T both satisfy BSTP, and 
  • all elements in the left subtree of T are less than the root of T, and 
  • the root of T is less than all elements in the right subtree of T.

We can take advantage of this property when looking up for a particular ordered object in the tree.  Instead of scanning the whole tree for the search target, we can compare the search target against the root element and narrow the search to the left subtree or the right subtree if necessary.  So in the worst possible case, the number of comparisons is proportional to the height of the binary tree.  This is a big win if the tree is balanced .  It can be proven that when a tree containing N elements is balanced, its height is at most a constant multiple of logN.  For example, the height of a balanced tree containing 10 ⁶ elements is at most a fixed multiple of 6.  Here is the definition of what a balanced tree is.

Definition of balanced tree

• An empty tree is balanced .
• A non-empty tree is balanced if and only if
  •  its subtrees are balanced and
  • the heights of the subtrees differ by a fixed constant or by a fixed constant factor.

A binary tree with  the BST property is called a binary search tree.  It can serve as an efficient way for storage/retrieval of data.  We are lead to the following question: how to create and maintain a binary search tree?  

2. binary search tree insertion

Suppose we start with an empty binary tree T and  a  Comparator that models a total ordering in a given set of objects S.  Then T clearly has the BST property with respect the Comparator ordering of S.  The following algorithm (visitor on binary trees) will allow us to insert elements of S into T and at the same time maintain the BST property for T.  This algorithm also works for binary search tree containing Comparable objects.