Trees, binary search trees and balance

Search, insert and sorted order

To find a key, start at the root and go left if the key is smaller, right if it is larger, until you find it or fall off the tree. Inserting is the same walk, attaching a new node where you fell off. Visiting the left subtree, then the node, then the right subtree gives every key in ascending order, which is what a hash table can't do:

Because keys are ordered, a BST also answers range queries ("all keys between 30 and 60"), the smallest or largest key, and "the next key after x", each in O(height) plus the size of the answer.

Why balance matters

A plain BST's shape depends entirely on the order of insertion. Random order gives a bushy tree of height a small multiple of log n. Sorted order, which is very common in practice (timestamps, auto-increment ids), gives a single path:

Building the sorted tree took about 50 million comparisons (0 + 1 + … + 9,999); in the shuffled tree no insert needed more than 29.

Balanced trees, at a high level

Self-balancing trees do a little extra work on each insert and delete to keep the height O(log n) whatever the order:

• AVL trees keep the heights of every node's two subtrees within one of each other, restoring that with rotations, small local re-wirings that preserve the BST order.
• Red-black trees colour nodes and enforce rules that keep the longest path at most twice the shortest. They rebalance less often than AVL trees. Java's TreeMap is one (its docs promise log(n) time for get, put and remove), and C++'s std::map is usually implemented as one.
• B-trees (and B+ trees) give each node hundreds of keys and children, sized to a disk page. With that much branching a table of millions of rows is only 3 or 4 levels deep, so a lookup reads only 3 or 4 pages. That is the default index type in PostgreSQL, MySQL's InnoDB and SQLite.

You will rarely implement one of these yourself. What matters is knowing that an ordered map gives you O(log n) operations plus ordering, a hash map gives you O(1) average without ordering, and an unbalanced tree gives you neither guarantee.