Binary search trees

One invariant

Each step discards one subtree, so a search costs the height of the tree — O(log n) if it is balanced, O(n) if it is not. Insert is the same walk: go down until you find an empty place, and put the node there.

function find(node, value) {
  while (node) {
    if (value === node.value) return node;
    node = value < node.value ? node.left : node.right;    // half the tree, gone
  }
  return null;
}

What it gives you that a hash table does not

If all you do is exact lookups, use a hash table — it is faster and simpler. A tree earns its place when order matters: range queries, "the next appointment after this one", leaderboards, autocomplete bounds, and every database index you have ever created.

Delete: the three cases

The third case is where people go wrong. You cannot simply promote a child, because both children would need the same place. The successor — the smallest thing on the right — is the only value that can sit there and keep the invariant, since it is bigger than everything on the left and smaller than everything else on the right.

And it is guaranteed to have no left child, which is why deleting it is always case 1 or case 2.

/* 1. a leaf              → remove it
   2. one child           → replace the node with that child
   3. two children        → replace its VALUE with the smallest value in the
                            right subtree (its in-order successor), then delete
                            that successor — which has at most one child */

function removeMin(node) {
  if (!node.left) return node.right;
  node.left = removeMin(node.left);
  return node;
}

The degeneration

Sorted input is the worst case, and sorted input is exactly what you get from an import, a migration, a replay of a log or an auto-incrementing id. Every operation becomes O(n) and the structure is worse than an array, because it also costs a pointer per node and gives up cache locality.

Inserting in random order gives an expected height of about 1.39·log₂ n, which is fine. Relying on your input being random is not engineering, which is why the next lesson exists.

insert 1, 2, 3, 4, 5 in order:

  1
   \
    2
     \
      3
       \
        4
         \
          5          height 5, not log 5. This is a linked list.

What it is under the name

You will rarely write one. What you will use constantly are its balanced descendants: a red-black tree behind std::map and Java’s TreeMap, a B-tree behind every relational database index, a skip list inside Redis’s sorted sets.

They all keep this same invariant and the same in-order walk. The difference is only in what they do after an insert to stop the picture above from happening.