AVL trees
A self-balancing binary search tree repairs its own shape after every change, guaranteeing O(log n) height. The AVL tree, from 1962, was the first.
Why balance
A plain BST can degrade to height n - 1, making operations O(n). Self-balancing BSTs enforce a structural rule after each insertion or deletion so the height stays O(log n) whatever order keys arrive in. Their search, insert, and delete are then O(log n) in the worst case.
The AVL invariant
Named after its inventors, Georgy Adelson-Velsky and Evgenii Landis, who published it in 1962, an AVL tree requires that at every node the heights of the left and right subtrees differ by at most 1. The balance factor is height(left) minus height(right), and it must be -1, 0, or +1 everywhere.
Why AVL trees are short
The sparsest possible AVL tree of height h has a number of nodes that grows like the Fibonacci numbers, so an AVL tree with n nodes has height at most about 1.44 log2(n). For a million keys, that is at most about 29 levels, compared with a possible million in an unbalanced BST.
Rotations
Balance is restored with rotations, local restructurings that preserve the BST ordering. A right rotation at node X makes X's left child Y the new subtree root, with X becoming Y's right child and Y's old right subtree becoming X's left subtree. A left rotation is the mirror image. Each rotation changes only a few pointers: O(1).
The four imbalance cases
After an insertion, walk back up updating heights. If a node's balance factor becomes +2 or -2, there are four cases. Left-left: rotate right once. Right-right: rotate left once. Left-right: rotate left at the left child, then right at the node. Right-left: rotate right at the right child, then left at the node. One single or double rotation fixes an insertion.
Deletion
Deletion removes the key as in a normal BST, then walks back up the path, rebalancing with the same rotations. Unlike insertion, deletion may need rotations at several levels, but there are at most O(log n) of them, so deletion remains O(log n).
Red-black trees and others
Red-black trees relax balance: nodes are coloured red or black, with rules such as no red node having a red child and every root-to-leaf path having the same number of black nodes, giving height at most 2 log2(n + 1). They rebalance with fewer rotations and are used in Java's TreeMap and many C++ std::map implementations. Splay trees, treaps, and skip lists are other balanced alternatives.
Worked example
Insert 10, 20, 30 into an empty AVL tree. After 30, node 10 has balance factor -2 (right subtree height 1, left height -1): a right-right case. A left rotation at 10 makes 20 the root with children 10 and 30, height 1. Inserting the same keys into a plain BST would give a chain of height 2, and continuing with 40, 50, 60 would keep growing the chain while the AVL tree stays logarithmic.
Key takeaways
Self-balancing BSTs keep height O(log n), guaranteeing O(log n) operations. AVL trees (1962) require subtree heights to differ by at most 1 at every node, giving height under about 1.44 log2(n). Rotations restructure locally in O(1) while preserving order. Insertion imbalances fall into left-left, right-right, left-right, and right-left cases fixed by single or double rotations. Deletion may rotate at several levels. Red-black trees, with height at most 2 log2(n + 1), rebalance more cheaply and back many standard libraries.
Flashcard
Maintains O(log n) height automatically
Check your understanding
After inserting into an AVL tree, a node's left child is too tall, and the new key went into that child's right subtree. How is it fixed?