Trees, Worked (rotations, B-trees, range trees)

What it shows, before any of it is named: a small swap that straightens a leaning tree, two rulebooks for when to make that swap, the same swap’s cousin for a tree stored on disk, and one more tree built for a different question entirely.

Before you start. You need a binary search tree: a box holding one key, pointing at up to two others, smaller keys down the left and bigger down the right, so left-or-right at each step narrows the search. Trees (BST, balancing, heaps, tries) built that and asked you to trust that balance keeps it fast - this lesson is the proof, by hand.