Balanced search trees

Overview

A balanced search tree is a BST that automatically keeps its height at O(log n) after every insert and delete, so operations never degrade to O(n). The main families are AVL trees (strict balance: subtree heights differ by at most 1), red-black trees (looser color rules, fewer rotations), and B-trees (many keys per node, used on disk).

Balance is restored with rotations: small local restructurings that change the shape of the tree while preserving the BST ordering. You rarely implement one in interviews, but you are expected to know why they exist, how rotations work, and which library types use them.

When to use it

• You need guaranteed O(log n) ordered operations, even on adversarial or sorted input.
• Ordered maps and sets with floor, ceiling, and range iteration (TreeMap, TreeSet).
• Sliding window problems that need ordered access (median, closest value) in O(log n).
• On-disk indexes where each node read is expensive (B-trees and B+ trees).

Problem patterns it solves

Where it is used in real software

Key terms

Balance factor (AVL)

height(left) - height(right); must be -1, 0, or 1.

Rotation

A local restructuring (left or right) that preserves inorder order.

Red-black rules

Root is black, no two reds in a row, every root-to-null path has the same number of black nodes.

B-tree order

Maximum children per node; high order means a shallow tree with few disk reads.

Skip list

Linked lists with express lanes; randomized alternative to balanced trees.

AVL insertion

1. 1
   Insert like a normal BST

   Walk down and attach the new leaf.

2. 2
   Update heights on the way up

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

3. 3
   Check the balance factor

   If it becomes 2 or -2, the node is unbalanced.

4. 4
   Left-Left or Right-Right case

   A single rotation (right or left) fixes it.

5. 5
   Left-Right or Right-Left case

   Rotate the child first, then the node (double rotation).

Inserting 10, 20, 30 into an AVL tree

A plain BST would become a chain: 10 -> 20 -> 30

One rotation turned a height-3 chain into a height-2 balanced tree. After n insertions, AVL height stays below about 1.44 log2(n).

Implementation

1class AVLNode {2  constructor(val) {3    this.val = val;4    this.left = null;5    this.right = null;6    this.height = 1;7  }8}9 10const height = (n) => (n ? n.height : 0);11const update = (n) => { n.height = 1 + Math.max(height(n.left), height(n.right)); };12const balance = (n) => height(n.left) - height(n.right);13 14function rotateRight(y) {15  const x = y.left;16  y.left = x.right;17  x.right = y;18  update(y);19  update(x);20  return x;21}22 23function rotateLeft(x) {24  const y = x.right;25  x.right = y.left;26  y.left = x;27  update(x);28  update(y);29  return y;30}31 32function insert(node, val) {33  if (!node) return new AVLNode(val);34  if (val < node.val) node.left = insert(node.left, val);35  else if (val > node.val) node.right = insert(node.right, val);36  else return node;37 38  update(node);39  const b = balance(node);40  if (b > 1 && val < node.left.val) return rotateRight(node);            // Left-Left41  if (b < -1 && val > node.right.val) return rotateLeft(node);           // Right-Right42  if (b > 1) { node.left = rotateLeft(node.left); return rotateRight(node); }   // Left-Right43  if (b < -1) { node.right = rotateRight(node.right); return rotateLeft(node); } // Right-Left44  return node;45}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Implementing a balanced tree in an interview when a library exists.

  Fix: Use TreeMap / TreeSet in Java; in JavaScript, explain the structure and use a sorted array with binary search for small inputs.

• Forgetting to update heights after rotation.

  Fix: Update the lower node first, then the new root.

• Integer overflow in range checks.

  Fix: Use long values when computing x - diff and x + diff.

Interview questions

Practice problems