Keeping a Tree Balanced

Every guarantee on the Binary Search Tree page - O(log n) search, insert, delete - was conditional on the tree actually being shallow. Section 8 there showed the condition can fail for free, just by inserting sorted data. This page is the fix: structures that do extra work on every insert and delete specifically so the height claim stays true no matter what order the data arrives in.

1. What "balanced" actually means

"Balanced" is not one definition - it is a family, and mixing them up is easy because they are all trying to say the same informal thing ("roughly as short as it could be").

Definition	Rule	Who uses it
Height-balanced	for every node, |height(left) - height(right)| <= 1	AVL trees; LeetCode 110 "Balanced Binary Tree"
Weight-balanced	for every node, neither subtree's node COUNT is more than a constant factor of the other's	weight-balanced trees, some persistent structures
Perfectly balanced	every level except possibly the last is completely full	complete and perfect trees

LeetCode 110 means the first one, checked at every node, not just the root:

⚠

Checking only the root's two subtrees is not enough

A tree can look balanced from the root and still fail the invariant three levels down. abs(height(root.left) - height(root.right)) <= 1 is a single check at a single node; LeetCode 110 requires it at every node. The efficient solution computes height bottom-up and returns a sentinel (-1, or any value height can never be) the instant one subtree is already found unbalanced, so the whole check is O(n) instead of O(n^2) from recomputing height at every node from scratch.

2. Rotations: the one primitive

A rotation is a local pointer rewrite around one edge: it promotes a child to take its parent's place and demotes the parent to be that child's child. Both trees below are the same tree read a different way - the inorder sequence is unchanged - but the height is not.

def rotate_right(y):

x = y.left

y.left = x.right # T2 moves from x's right to y's left

x.right = y # y drops down to become x's right child

return x # x is the new subtree root

rotate_left is the mirror image: it promotes the right child instead. The inorder order surviving the rewrite is exactly why a rotation is safe to use inside a BST - x < T2 < y < T3 before the rotation, and reading the "after" tree inorder gives the identical sequence.

A rotation trades depth for depth, never for correctness.

It moves one subtree (T2 above) up one level and another node (y) down one level, and that is the entire effect. Nothing is copied, no values change, and the BST invariant from the previous page is preserved automatically - which is why every self-balancing BST can be built as "the usual insert/delete, plus rotations applied afterward."

3. AVL trees

An AVL tree enforces the height-balanced rule from section 1 after every insert and delete: walk back up from the changed node, and the moment a node's balance factor (height(left) - height(right)) leaves {-1, 0, 1}, fix it with one or two rotations.

Balance factor at the unbalanced node	Shape of the problem	Fix
+2, and the left child is also left-heavy (>= 0)	"LL" - a straight left-left chain	one right rotation
-2, and the right child is also right-heavy (<= 0)	"RR" - a straight right-right chain	one left rotation
+2, and the left child is right-heavy (< 0)	"LR" - a zigzag	left-rotate the child, then right-rotate the node
-2, and the right child is left-heavy (> 0)	"RL" - a zigzag	right-rotate the child, then left-rotate the node

Each of the four cases costs at most two rotations, and a single insert or delete can only unbalance nodes on the path back to the root, so a fix-up is O(log n) rotations at worst - in fact insertion needs at most one fix (one straight case or one zigzag), because the first rotation you apply restores the height the subtree had before the insert.

AVL's invariant is the strictest of the self-balancing trees: height is bounded by roughly 1.44 * log2(n + 2), barely above the log2 n of a perfect tree. That makes it the fastest option for read-heavy workloads - every search is as short as a BST's height can possibly get - at the cost of more rotation work on every write than a looser structure needs.

def height(node):

return node.height if node else -1 # empty subtree has height -1

 

def balance_factor(node):

return height(node.left) - height(node.right)

 

def rebalance(node):

node.height = 1 + max(height(node.left), height(node.right))

bf = balance_factor(node)

if bf > 1: # left-heavy

if balance_factor(node.left) < 0:

node.left = rotate_left(node.left) # LR: straighten first

return rotate_right(node)

if bf < -1: # right-heavy

if balance_factor(node.right) > 0:

node.right = rotate_right(node.right) # RL: straighten first

return rotate_left(node)

return node # already balanced

⚠

Rebalancing on the way up, not the way down

A recursive AVL insert has to call rebalance on its way back OUT of the recursion, after the child call returns - not on the way in. The insert has to actually happen first, so that the subtree's height is up to date when rebalance checks it. node.left = rebalance(insert(node.left, val)) is the whole pattern: insert into the child, rebalance what comes back, then let the parent's own rebalance call see the corrected height.

4. Red-black trees

A red-black tree balances less strictly, in exchange for touching fewer nodes on the way back up. Every node is colored red or black under four rules:

Rule	What it prevents
The root is black	a degenerate edge case in the other rules
A red node's children are both black (no two reds in a row)	a run of red nodes acting like an unbalanced chain
Every path from a node to any descendant None passes through the same number of black nodes	one path being disproportionately long in black nodes
None leaves count as black	the base case for rule 3

A valid red-black tree: every red node (filled) has two black children, and every root-to-null path passes through exactly two black nodes, whichever route you take.

These four rules together guarantee the longest root-to-leaf path is never more than twice the shortest one - looser than AVL's near-log2 n bound, but still O(log n), and cheap to restore: an insert needs at most 2 rotations plus some recoloring, a delete at most 3. That is why red-black is the default choice for write-heavy general-purpose libraries: it does less work per mutation than AVL, at the cost of search paths that are up to twice as long.

⚠

"Looser" does not mean "less balanced" in a useful sense

Red-black's 2x height bound sounds like a weaker guarantee than AVL's 1.44x, but both are O(log n) - the difference is a constant factor, not an order of growth. The two structures do not disagree about whether the tree stays shallow; they disagree about how much rebalancing work they are willing to spend keeping it that way. Choosing between them is a read/write-ratio question, never a correctness one - a red-black tree is never at risk of degenerating the way an unbalanced BST from the previous page can.

	AVL	Red-black
Height bound	~1.44 log2 n	~2 log2 n
Search	faster (tighter height)	slightly slower
Insert / delete	more rotations, stricter rebalancing	fewer rotations, cheaper rebalancing
Best suited to	read-heavy workloads	write-heavy / general-purpose workloads
Real-world example	less common in general libraries	std::map, Java TreeMap, Linux kernel's CFS scheduler

5. B-trees, and why disks change the answer

AVL and red-black trees both minimize the number of comparisons. That is the right thing to minimize when comparisons are the expensive step - a value already sitting in RAM. It stops being the right thing the moment the data lives on disk (or, at cloud scale, behind a network round trip), because then the expensive step is not "compare two values," it is "fetch a page."

A B-tree node holds not one key but many - often hundreds, sized to fill exactly one disk page - and has that many-plus-one children. Fanout in the hundreds means a tree over billions of rows is only 3-4 levels deep, so a lookup costs 3-4 disk reads regardless of how many keys sit inside each node, because the comparisons within a fetched page happen in memory and are practically free next to the read that brought the page in.

A binary tree does the opposite of what a disk wants. Its whole design minimizes comparisons by keeping fanout at 2, which maximizes height for a given n - exactly backwards from "fewest disk reads," which wants fanout as high as possible and height as low as possible. That mismatch, not raw speed, is the actual reason database engines and filesystems use B-trees (or the B+-tree variant) instead of a red-black tree, even though both give O(log n).

6. Which one you actually use

You almost never implement a self-balancing tree by hand in an interview. The skill that matters is recognizing which library structure already is one, and recognizing when an input is adversarial enough to need one at all.

You reach for	What it actually is	Note
Python dict / set	a hash table, not a tree	no ordering guarantee at all; do not expect sorted iteration
sortedcontainers.SortedList / SortedDict	a list of small sorted blocks (B-tree-ish, not node-and-pointer)	Python's practical answer to 'I need an ordered structure'
C++ std::map / std::set	a red-black tree	ordered iteration, O(log n) everything, guaranteed by the standard
Java TreeMap / TreeSet	a red-black tree	same guarantee as std::map
A database index	a B+-tree (keys only in leaves, leaves linked for range scans)	built for disk pages, not comparisons - section 5
An interview answer	usually 'a plain BST, and here is why the input order matters'	implementing AVL/red-black from scratch is rare; recognizing the adversarial-order trap is common

The practical skill this whole page is training is spotting the trap from Binary Search Tree §8: an interviewer who says "insert these values in this exact order" and then hands you sorted data is testing whether you notice a plain BST just became a linked list, not whether you can code AVL rotations from memory.

Where to go next

• Binary Search Tree - the invariant and operations these structures all preserve while rebalancing.
• Tree Anatomy - the precise vocabulary (complete, perfect, full) behind "perfectly balanced".
• Trees in the Wild - where B-trees, tries, and the rest actually show up outside of interview questions.
• Practice: Binary Search Tree problems.