Self-balancing trees
Parts, in publishing order
- Self-balancing binary search trees, part 1: trees and binary trees
What a tree is, the vocabulary for talking about one, and the properties and kinds of binary trees, as groundwork for balanced search trees.
- Self-balancing binary search trees, part 2: why a BST needs to be balanced
How a binary search tree orders its keys, why that helps a runway-reservation system, why tree height matters, and what balancing has to guarantee.
- Self-balancing binary search trees, part 3: AVL trees
The AVL invariant, the proof that it keeps tree height at O(log n), and how insertions and deletions restore the invariant with rotations.