The four tree types
- Binary search tree — the plain one. Every value goes left if it is smaller than the node and right if it is larger, until it reaches an empty spot. Fast when the values arrive jumbled; when they arrive sorted the tree becomes a stick and searching it is no better than scanning a list. That problem is why the other three exist.
- AVL tree— stores a height on every node and keeps every subtree height-balanced. When an insertion pushes a node's balance to ±2, one rotation (or two, when the unbalanced node and its child lean opposite ways) puts it right.
- Red-black tree— colours the nodes instead of measuring them. A new node arrives red; if that puts two reds in a row, the tree either recolours or rotates, depending on the colour of the parent's sibling.
- 2-3 tree — allows a node to hold two values and three children, so it never has to rotate. A full leaf splits and pushes its median up to the parent, which is how every leaf stays on the same level.
Running an insertion
- Type a value and insert it, or paste a whole comma-separated list to insert one after another. The course's own worked sequences load with one click.
- Each insertion becomes a series of steps you can play, pause, step through, and scrub backwards — the comparisons on the way down, then the rebalancing, each with a sentence saying what is happening and why.
- The plain binary search tree also supports removal: a leaf just goes, a node with one child is replaced by that child, and a node with two children is replaced by its inorder successor.
Scope
- Insertion is the focus, because that is where balancing is decided. Removal from the AVL, red-black, and 2-3 trees is left to the course notes, as are the proofs of their height bounds.
- Your values never leave the browser — see About & privacy.