C++ Notes: Binary Search Trees

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

For large values of N, differences in efficiency can become dramatic. For example, a linear search of an array takes 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 takes 500,000 comparisons vs 20 comparisons for binary search. This matters. But there are other issues. For example, inserting in a sorted list is an O(N) operation because of all the elements that have to be moved, so for frequent updates there is much less advantage to a sorted array.

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

Because insertion in a tree is a matter of changing links and not moving any 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).

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 implemenation for the STL map, multimap, set, and multiset.

Related Pages

Next: Binary Tree Traversal.