22. How does an AVL tree stay balanced?
HardTrees
Technical
Show model answer
An AVL tree keeps, for every node, the heights of its two subtrees within 1 of each other. After an insert or delete, it walks back up and fixes any node whose balance factor becomes ±2 with a rotation: single rotations for the left-left and right-right cases, and double rotations for left-right and right-left.
This guarantees height O(log n), so search, insert and delete are O(log n). Red-black trees allow slightly more imbalance in exchange for fewer rotations on updates.