Balanced Search Trees

A binary search tree gives $O(\log n)$ search, insert, and delete — but only if the tree stays roughly balanced. Insert 1, 2, 3, 4, 5 into a plain BST in that order and every new node becomes the right child of the previous one: the tree degenerates into a straight line, height $n$, and every operation is $O(n)$ — you've built an expensive linked list. Balanced search trees (AVL trees, red-black trees, B-trees) add bookkeeping rules that automatically restructure the tree on every insert or delete, guaranteeing height stays $O(\log n)$ regardless of what order the data arrives in.

The idea: rebalance after every change, using local rotations

The core operation across balanced tree types is a rotation — a local restructuring that swaps a parent and one of its children while preserving the BST ordering property (left subtree smaller, right subtree bigger), and typically shortens the tree's height on one side.

Different tree types use different rules for when to rotate:

• AVL trees track the height difference (balance factor) between each node's two subtrees and rotate whenever that difference exceeds 1. This gives the tightest guaranteed balance — height never exceeds about $1.44 \log_2 n$ — at the cost of more frequent rotations on inserts.
• Red-black trees color each node red or black and enforce looser rules (no two reds in a row, every root-to-leaf path has the same black-node count). Height stays within $2 \log_2(n+1)$ — a looser bound than AVL, but fewer rotations on average, which is why most language standard libraries (std::map in C++, TreeMap in Java) use red-black trees rather than AVL.
• B-trees let each node hold multiple keys and children, which reduces tree height dramatically and matches how disk/page-based storage reads data in blocks — this is why database indexes use B-trees (or B+-trees) instead of binary trees.

Worked example: an AVL rotation after a sorted insert

Insert 10, then 20, then 30 into an empty AVL tree.

• Insert 10: tree is just 10.
• Insert 20: becomes 10's right child. Tree: 10 → 20. Balance factor at 10 is now -1 (right subtree taller by 1) — still within tolerance.
• Insert 30: becomes 20's right child. Now 10's right subtree has height 2, left subtree height 0 — balance factor -2, over the limit. AVL performs a left rotation at 10: 20 becomes the new root, 10 becomes its left child, 30 stays its right child.

Result: a balanced tree 20 with children 10 and 30 — height 2 instead of the height-3 chain a plain BST would have produced from the same sorted input. Every future insert or search on this small example now touches at most 2 nodes instead of 3, and the gap widens as $n$ grows: $O(\log n)$ versus $O(n)$.

Where it shows up

Interviews rarely ask you to implement AVL or red-black rotations from scratch — the expected knowledge is recognizing why they're needed (the sorted-insert degeneration) and knowing which language structure to reach for (sortedcontainers in Python, std::map/std::set in C++, both backed by balanced trees) when a problem needs ordered data with fast insert, delete, and range queries together. In quant systems, this is the structure underneath an in-memory order book keyed by price level, where prices arrive in no particular order but need fast insertion, deletion, and "best bid/offer" (min/max) queries — and it's the reason database indexes on time-series or tick data use B-trees rather than plain binary trees, since B-trees are tuned for the block-based reads a disk or SSD actually performs.