Core Data Structures

Balanced Trees

AVL trees, red-black trees, and B-trees all solve the same problem — a plain BST's height is not guaranteed — by enforcing a structural invariant after every insert/delete that keeps height at Θ(log n) no matter the insertion order.

AVL tree: for every node, the heights of its two subtrees differ by at most 1 — the strictest and most rigidly balanced of the common schemes
Red-black tree: a looser balance (color rules on nodes) that needs fewer rotations per update — this is what Java's TreeMap/TreeSet use internally
Both guarantee height Θ(log n) for n nodes, so search/insert/delete are all O(log n) worst case, not just on average
Rebalancing after insert/delete uses rotations — local, O(1) restructurings that preserve the BST ordering invariant
B-trees generalize the idea to many children per node, minimizing disk/page reads — the standard structure inside database indexes

A rotation is the single mechanical operation every balanced-tree scheme is built from: pick an edge between a node and its child, and pivot around it, promoting the child to take the parent's place while preserving the in-order sequence of all keys. A single rotation is O(1); an AVL insert triggers at most O(log n) rotations up the path from the new leaf back to the root (in practice usually just one or two), which is why insertion stays O(log n) overall including the rebalancing.

Balance schemes compared
Scheme	Balance rule	Rotations per insert/delete	Where you meet it
AVL	Subtree heights differ by ≤ 1	More (stricter balance)	Rare in stdlib; used when reads dominate writes
Red-black	Coloring + path-length rules	Fewer (amortized O(1))	`TreeMap`, `TreeSet`, C++ `std::map`
B-tree	Many keys per node, all leaves same depth	Node splits/merges	Database indexes, filesystems

A right rotation — the O(1) building block

//        y                    x
//       / \                  / \
//      x   C   -- rotate --> A   y
//     / \      right(y)         / \
//    A   B                     B   C
static TreeNode rotateRight(TreeNode y) {
    TreeNode x = y.left();
    TreeNode b = x.right();
    TreeNode newY = new TreeNode(y.val(), b, y.right());   // y keeps B and C
    return new TreeNode(x.val(), x.left(), newY);          // x takes A and new y
}