Binary Search

Binary Search is built around the foundation of Divide-and-Conquer and its fundamental idea is to locate an item in an ordered list of items in a recursive way.

It is worth noted that performing binary search operation in whatever structures of ordered items are the same given the premise traversing through the items is relatively costless. Whereas, performing INSERTION or DELETION operations in commonly seen sorted structures such as Array or List takes up to Ο(n) complexity; While a prevalent implementation that involves a concept of Tree, Binary Search Tree could boost the INSERTION and DELETION operations, meanwhile rapidly solve searching problems in a simple yet robust way.

Note: If only demanding fast lookup operation in the algorithm design, the Hash Table would be better given its Ο(1) running time.

Pseudocode

BINARY_SEARCH(array, start, end, target)
  middle := (start + end) / 2
  if array[middle] = target
    return array[middle]
  else if array[middle] > target
    BINARY_SEARCH(array, start, middle - 1, target)
  else if array[middle] < target
    BINARY_SEARCH(array, middle + 1, end, target)

Binary Search Tree (BST)

BST is organized on the basis of a structure of binary tree and is a rooted tree; It could be represented in a dynamic list wherein the nodes contain information about pointer to the left, right and parent subtree.

Figure 1. Binary Search Tree Graphical Representation

The design idea of BST is that given every possible node x in the tree, all keys in the left subtree are smaller than x while all keys in the right subtree are larger than x.

Traversal of BST

Traverse through an entire structure of BST recursively or iteratively has three distinct ways: in-order tree walk, pre-order tree walk and post-order tree walk.

• In-order Tree Walk

The output key entries of sub-trees follows the pattern of left subtree, root and right subtree. e.g. the In-order Tree Walk of Figure 1 binary tree yields 1, 3, 4, 6, 7, 8, 10, 13, 14.

• Pre-order Tree Walk

The output key entries of sub-trees follows the pattern of root, left subtree and right subtree. e.g. the Pre-order Tree Walk of Figure 1 binary tree yields 8, 3, 1, 6, 4, 7, 10, 14, 13.

• Post-order Tree Walk

The output key entries of sub-trees follows the pattern of left subtree, right subtree and root. e.g. the Post-order Tree Walk of Figure 1 binary tree yields 1, 4, 7, 6, 3, 13, 14, 10, 8.

Searching Performance

Basic operations cost of a Binary Search Tree is proportional to the height of such tree. Given a randomly built binary search tree with n keys, it is expected to have a tree of height log(n) and the searching consumption is Θ(log n).

It requires a worst-case running time of Ο(n) if the arriving sequence of data is monotonically increasing or decreasing during the binary tree formation. Additionally, during the INSERTION or DELETION operations on the tree, there is possibility that properties of binary tree are violated. Therefore, it is necessary to form a tree structure with a relative balanced entry distribution called Balanced Binary Search Tree (BBST), which means both sides of the tree or subtree have a relative same height. In order to maintain such property of BBST even during massive INSERTION or DELETION operations on the tree, a special Rotation operation comes into play.

Rotation

Rotations are called when the BBST properties are violated. There are two kinds of rotations: left rotation and right rotation; they both operate on the pointers among the nodes to maintain the balanced features of the tree.

• Left Rotation

This method is called when (in AVL Tree, height difference between the right subtree and the left subtree is more than 1).

As shown in figure 2, left rotate operation can be formalized as LEFT-ROTATE(T, y), which transforms the right child of y to be the parent of y in the new tree and assigns the β child of x to y.

LEFT_ROTATE(T, y)
  x = y.right
  y.right = x.left
  if x.left ≠ null
    x.left.parent = y
  x.parent = y.parent
  if y.parent == null
    T.root = x
  else if y == y.parent.left
    y.parent.left = x
  else
    y.parent.right = x
  x.left = y
  y.parent = x

• Right Rotation

This method is called when (in AVL Tree, the height difference between the left subtree and the right subtree is more than 1).

As shown in figure 2, right rotate operation can be formalized as RIGHT-ROTATE(T, x), which transforms the left child of x to be the parent of x in the new tree and assigns the β child of y to x.

RIGHT_ROTATE(T, x)
  y = x.left
  x.left = y.right
  if y.right ≠ null
    y.right.parent = x
  y.parent = x.parent
  if x.parent == null
    T.root = y
  else if x.parent.left = x
    x.parent.left = y
  else
    x.parent.right = y
  y.right = x
  x.parent = y

Figure 2. Binary Search Tree Rotations

Prevalent Implementations of Balanced Search Tree

There are popular implementations like AVL Tree and Red-Black Tree in practice, and they both propose solutions to help search operation obtain a guaranteed Θ(log n) complexity.

• AVL Tree - a first balanced binary search tree structure ever invented.
• Red Black Tree - a sophisticated while popular balanced search tree in various systems.
• Splay Tree - a self-adjusting structure to achieve a balanced search tree.
• 2-3 Tree - a distinct tree structure designed to provide BBST solution with high performance for INSERTION operation.
• B-Tree - a practical data structure designed for the database.