C++ Notes: Binary Search Trees

O(log N) can be MUCH better than O(N)

For large values of N, differences in efficiency are dramatic. For example, a linear search of an array requires n/2 comparisons on the average. If the array is sorted, it's possible to do a binary search with an average of log base 2 comparisons. For small values of n this is not an important difference. For example, for 32 items it takes 16 comparisons for linear search vs 5 for a binary search. The extra 11 comparisons are negligible.

In contrast to this, if n is a million, a linear search requires 500,000 comparisons vs 20 comparisons for binary search. This is significant, but there are other issues. For example, inserting or deleting in a sorted list is an O(N) operation because, on the average, half of the elements that have to be moved, so for frequent updates there is much less advantage to a sorted array. Binary search is also not possible on a linked list because random access is required.

Binary search trees: O(log N) search and insert

Because insertion in a tree is a matter of changing links and not moving data, binary search trees have the speed advantages of sorted arrays for searching plus fast inserting (O(log n) to find the insertion point and O(1) to insert). A fairly well balanced tree can be maintained with so-called red-black trees.

Typical binary tree node

struct tree_node {
    tree_node *left;   // left subtree has smaller elements
    tree_node *right;  // right subtree has larger elements
    int data;
};

Standard Template Library uses binary search trees

Binary search trees are so good, they are the underlying implementation for the STL map, multimap, set, and multiset.

Related Pages

Next: Binary Tree Traversal.