Data Structures with Generic Types in C++/

...

/

BinarySearchTree: An Unbalanced Binary Search Tree

BinarySearchTree: An Unbalanced Binary Search Tree

Discover how to search, add or remove an element in the BinarySearchTree.

We'll cover the following...

A BinarySearchTree is a special kind of binary tree in which each node, u, also stores a data value, u.x, from some total order. The data values in a binary search tree obey the binary search tree property: For a node, u, every data value stored in the subtree rooted at u.left is less than u.x and every data value stored in the subtree rooted at u.right is greater than u.x. An example of a BinarySearchTree is shown below.

A binary search tree
A binary search tree

Searching

The binary search tree property is extremely useful because it allows us to quickly locate a value, x, in a binary search tree. To do this we start searching for x at the root, r. When examining a node, u, there are three cases:

  1. If x < u.x, then the search proceeds to u.left
  2. If x > u.x, then the search proceeds to u.right
  3. If x = u.x, then we have found the node u containing x

The search terminates when Case 3 occurs or when u = nil. In the former case, we found x. In the latter case, we conclude that x is not in the binary search tree.

T findEQ(T x) {
  Node u = r;
  while (u != nil) {
    int comp = compare(x, u.x);
    if (comp < 0)
      u = u.left;
    else if (comp > 0)
      u = u.right;
    else
      return u.x;
  }
  return null;
}

Visual demonstration of search

Two examples of searches in a binary search tree are shown in the illustration below.

As the second example shows, even if we don’t find x in the tree, we still gain some valuable information. If we look at the last node, u, at which Case 1 occurred, we see that u.x is the smallest value in the tree that is greater than x. Similarly, the last node at which Case 2 occurred, contains the largest value in the tree that is less than x. Therefore, by keeping track of the last node, z, at which Case 1 occurs, a BinarySearchTree can implement the find(x) operation that returns the smallest value stored in the tree that is greater than or equal to x:

T find(T x) {
  Node w = r, z = nil;
  while (w != nil) {
    int comp = compare(x, w.x);
    if (comp < 0) {
      z = w;
      w = w.left;
    } else if (comp > 0) {
      w = w.right;
    } else {
      return w.x;
    }
  }
  return z == nil ? null : z.x;
}

Addition

To add a new value, x, to a BinarySearchTree, we first search for x. If ...