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.