Binary trees

How to add a name to a sorted list without shifting all the others

A binary search tree keeps items sorted and cheap to add to. Each node (a record with a key and two links) has at most two children: smaller keys go in its left branch, larger keys in its right.

Take keys 50, 30, 70, 20, 40, 60, 80, with 50 as the root (top node). To add 45, a sorted array must shift every later item. The tree walks down and hangs 45 as a new leaf (a node with no children); nothing moves.

Reading the tree left branch, then node, then right branch (an in-order walk) gives 20, 30, 40, 45, 50, 60, 70, 80, the keys in sorted order.

Binary trees

Java's TreeMap and C++'s std::map hand back keys in sorted order

Java's TreeMap and the usual C++ std::map are built on red-black trees, a kind of binary search tree that keeps itself balanced. That is why looping over one gives keys in sorted order, while a hash map gives them in no useful order.

Ordered keys also allow queries a hash table can't do quickly: the smallest key, the next key after 45, or all keys between 40 and 60. The price is O(log n) per lookup instead of about one step.

Binary trees

Each comparison skips a whole branch you never visit

Each comparison says which branch holds the key, ruling out the other branch and all below it. It is binary search with the halves stored as links, so an insert attaches one node instead of moving items.

Speed depends on height. Insert already-sorted keys (1, 2, 3, …) and each goes right of the last, so the tree becomes a linked list: a million keys, up to a million steps, O(n).

Balanced trees such as red-black and AVL trees prevent this with rotations (relinking a few nodes) after inserts, keeping the height near log₂ n.