Balanced Trees (AVL, Red-Black) — DSA

Balanced Trees (AVL & Red-Black)

A Binary Search Tree gives O(log n) search — but only when it stays balanced. Insert sorted data into a plain BST and it degenerates into a linked list, making every operation O(n). Balanced BSTs guarantee O(log n) in the worst case by automatically re-balancing after insertions and deletions.

Why Balancing Matters

Consider inserting 1, 2, 3, 4, 5 into a plain BST:

Text

Plain BST (degenerate — like a linked list):

1
 \
  2
   \
    3
     \
      4
       \
        5

search(5) → 5 comparisons   O(n)

Balanced BST (AVL):

        3
       / \
      2   4
     /     \
    1       5

search(5) → 3 comparisons   O(log n)

Note

The height of a perfectly balanced BST with n nodes is floor(log₂ n). A degenerate BST has height n−1. With 1 million nodes that is the difference between 20 comparisons and 999,999.

Operation	Degenerate BST	Balanced BST
Search	O(n)	O(log n)
Insert	O(n)	O(log n)
Delete	O(n)	O(log n)
Min / Max	O(n)	O(log n)

AVL Trees

An AVL tree (Adelson-Velsky & Landis, 1962) is the first self-balancing BST ever invented. The invariant is simple: for every node, the heights of its left and right subtrees may differ by at most 1. This difference is called the balance factor.

Text

Balance Factor = height(left subtree) − height(right subtree)

Valid values: −1, 0, +1
Any other value → rebalance required

Example:
        50  (bf = 0)
       /  \
     30    70  (bf = 0 each)
    /  \
  20   40  (bf = 0 each)

After inserting 10:
        50  (bf = +2  ← violation!)
       /  \
     30    70
    /  \
  20   40
  /
10

AVL Rotations

There are four rotation cases. Each restores the balance factor invariant in O(1) time.

Case 1 — Left-Left (LL): right rotation

The inserted node is in the left subtree of the left child. Fix: rotate the unbalanced node right.

Text

Before (z is unbalanced, bf = +2):        After right rotation:

        z                                   y
       / \                                / \
      y   T4    rightRotate(z)           x   z
     / \         ────────────>          / \ / \
    x   T3                            T1 T2 T3 T4
   / \
  T1  T2

Case 2 — Right-Right (RR): left rotation

The inserted node is in the right subtree of the right child. Fix: rotate the unbalanced node left.

Text

Before (z is unbalanced, bf = −2):        After left rotation:

  z                                           y
 / \                                        / \
T1  y         leftRotate(z)                z   x
   / \        ──────────────>             / \ / \
  T2  x                                 T1 T2 T3 T4
     / \
    T3  T4

Case 3 — Left-Right (LR): left-rotate child, then right-rotate root

Text

Before:                  After leftRotate(y):      After rightRotate(z):

    z                         z                             x
   / \                       / \                          /   \
  y   T4                    x   T4                        y     z
 / \           ──────>     / \           ──────>         / \   / \
T1  x                     y   T3                       T1 T2 T3 T4
   / \                   / \
  T2  T3               T1  T2

Case 4 — Right-Left (RL): right-rotate child, then left-rotate root

Text

Before:                  After rightRotate(y):     After leftRotate(z):

  z                             z                           x
 / \                           / \                        /   \
T1  y          ──────>        T1  x         ──────>       z     y
   / \                           / \                     / \   / \
  x   T4                       T2  y                   T1 T2 T3 T4
 / \                               / \
T2  T3                            T3  T4

AVL Tree — JavaScript Implementation

class AVLNode {
  constructor(val) {
    this.val = val;
    this.left = this.right = null;
    this.height = 1;
  }
}

class AVLTree {
  height(n) { return n ? n.height : 0; }

  bf(n) { return n ? this.height(n.left) - this.height(n.right) : 0; }

  updateHeight(n) {
    n.height = 1 + Math.max(this.height(n.left), this.height(n.right));
  }

  rightRotate(z) {
    const y = z.left, T3 = y.right;
    y.right = z;
    z.left  = T3;
    this.updateHeight(z);
    this.updateHeight(y);
    return y;                   // new root of this subtree
  }

  leftRotate(z) {
    const y = z.right, T2 = y.left;
    y.left  = z;
    z.right = T2;
    this.updateHeight(z);
    this.updateHeight(y);
    return y;
  }

  insert(node, val) {
    // 1. Standard BST insert
    if (!node) return new AVLNode(val);
    if (val < node.val)      node.left  = this.insert(node.left,  val);
    else if (val > node.val) node.right = this.insert(node.right, val);
    else return node;           // duplicate — ignore

    // 2. Update height
    this.updateHeight(node);

    // 3. Check balance factor
    const balance = this.bf(node);

    // LL
    if (balance > 1 && val < node.left.val)
      return this.rightRotate(node);
    // RR
    if (balance < -1 && val > node.right.val)
      return this.leftRotate(node);
    // LR
    if (balance > 1 && val > node.left.val) {
      node.left = this.leftRotate(node.left);
      return this.rightRotate(node);
    }
    // RL
    if (balance < -1 && val < node.right.val) {
      node.right = this.rightRotate(node.right);
      return this.leftRotate(node);
    }
    return node;
  }

  add(val) { this.root = this.insert(this.root, val); }
}

// Demo
const avl = new AVLTree();
[1, 2, 3, 4, 5, 6, 7].forEach(v => avl.add(v));
// Result: perfectly balanced tree of height 3

Tip

After every insert trace the path from the newly inserted leaf back to the root — only the first unbalanced ancestor needs fixing. After one rotation the tree is balanced again; you do not need to keep climbing.

Red-Black Trees

A Red-Black tree is a BST where every node is coloured red or black, and five invariants are maintained to keep the tree approximately balanced. The height is at most 2 log₂(n+1), guaranteeing O(log n) operations.

Red-Black Properties

Every node is either RED or BLACK.
The root is BLACK.
Every NIL leaf (null sentinel) is BLACK.
If a node is RED, both its children are BLACK (no two consecutive reds).
All paths from any node to its descendant NIL leaves contain the same number of BLACK nodes (the "black-height").

Text

Valid Red-Black tree (B = black, R = red):

              13(B)
             /     \
           8(R)    17(R)
          /   \    /   \
        1(B) 11(B)15(B) 25(B)
          \                \
          6(R)            27(R)

Black-height of root = 2 (counting only black nodes on any root→NIL path).
Property 4 check: no red node has a red child. ✓
Property 5 check: every root→NIL path has exactly 2 black nodes. ✓

Insertions and Recolouring

New nodes are always inserted as RED (to avoid violating property 5 immediately). After insertion we fix up the tree by applying one of three cases depending on the colour of the new node's uncle:

Case	Uncle colour	Fix
1	RED	Recolour parent & uncle black, grandparent red; move up
2	BLACK (triangle)	Rotate parent toward new node (converts to Case 3)
3	BLACK (line)	Rotate grandparent away; swap parent/grandparent colours

Note

Unlike AVL trees, Red-Black trees may perform at most 2 rotations per insertion (and at most 3 per deletion). AVL trees may do O(log n) rotations after deletion. Red-Black trees are therefore preferred when writes are frequent.

AVL vs Red-Black — Side-by-Side Comparison

Property	AVL Tree	Red-Black Tree
Balance guarantee	Height ≤ 1.44 log₂(n+2)	Height ≤ 2 log₂(n+1)
Rotations per insert	O(log n) in worst case	At most 2
Rotations per delete	O(log n)	At most 3
Extra storage	1 integer (height) per node	1 bit (colour) per node
Search speed	Slightly faster (stricter balance)	Slightly slower
Insert/delete speed	Slightly slower (more rotations)	Slightly faster
Best for	Read-heavy workloads	Write-heavy workloads
Used in	Some DBs, game engines	Linux kernel, Java TreeMap, C++ std::map

Red-Black Tree — JavaScript Implementation (Insert)

const RED = 'RED', BLACK = 'BLACK';

class RBNode {
  constructor(val) {
    this.val = val;
    this.color = RED;
    this.left = this.right = this.parent = null;
  }
}

class RedBlackTree {
  constructor() { this.root = null; }

  // ── rotations ──────────────────────────────────────────
  leftRotate(x) {
    const y = x.right;
    x.right = y.left;
    if (y.left) y.left.parent = x;
    y.parent = x.parent;
    if (!x.parent)          this.root = y;
    else if (x === x.parent.left) x.parent.left  = y;
    else                          x.parent.right = y;
    y.left  = x;
    x.parent = y;
  }

  rightRotate(x) {
    const y = x.left;
    x.left = y.right;
    if (y.right) y.right.parent = x;
    y.parent = x.parent;
    if (!x.parent)           this.root = y;
    else if (x === x.parent.right) x.parent.right = y;
    else                           x.parent.left  = y;
    y.right = x;
    x.parent = y;
  }

  // ── insert ─────────────────────────────────────────────
  insert(val) {
    const z = new RBNode(val);

    // Standard BST insert
    let y = null, x = this.root;
    while (x) {
      y = x;
      x = val < x.val ? x.left : x.right;
    }
    z.parent = y;
    if (!y)               this.root = z;
    else if (val < y.val) y.left    = z;
    else                  y.right   = z;

    this.fixInsert(z);
  }

  fixInsert(z) {
    while (z.parent && z.parent.color === RED) {
      const p  = z.parent;
      const gp = p.parent;
      if (!gp) break;

      if (p === gp.left) {
        const uncle = gp.right;
        if (uncle && uncle.color === RED) {
          // Case 1: uncle is red — recolour
          p.color     = BLACK;
          uncle.color = BLACK;
          gp.color    = RED;
          z = gp;
        } else {
          if (z === p.right) {
            // Case 2: triangle — rotate parent
            z = p;
            this.leftRotate(z);
          }
          // Case 3: line — rotate grandparent
          z.parent.color         = BLACK;
          z.parent.parent.color  = RED;
          this.rightRotate(z.parent.parent);
        }
      } else {
        // Mirror image (parent is right child)
        const uncle = gp.left;
        if (uncle && uncle.color === RED) {
          p.color     = BLACK;
          uncle.color = BLACK;
          gp.color    = RED;
          z = gp;
        } else {
          if (z === p.left) {
            z = p;
            this.rightRotate(z);
          }
          z.parent.color         = BLACK;
          z.parent.parent.color  = RED;
          this.leftRotate(z.parent.parent);
        }
      }
    }
    this.root.color = BLACK;   // property 2: root is always black
  }
}

// Demo
const rb = new RedBlackTree();
[7, 3, 18, 10, 22, 8, 11, 26].forEach(v => rb.insert(v));

Practical Use in Standard Libraries

C++ std::map and std::set — Red-Black tree; O(log n) ordered iteration
Java TreeMap and TreeSet — Red-Black tree; guarantees sorted key order
Linux kernel's Completely Fair Scheduler — Red-Black tree tracks runnable tasks by virtual runtime
Nginx timer management — Red-Black tree for scheduled events
AVL trees appear in some database index implementations where reads dominate

Interview Problems

Problem 1 — Height of a balanced BST: Given n nodes, what is the minimum possible height?

// Minimum height = floor(log2(n))
function minHeight(n) {
  return Math.floor(Math.log2(n));
}
// n = 7  → 2
// n = 15 → 3

Problem 2 — Check if a BST is height-balanced (AVL property):

function isBalanced(root) {
  function check(node) {
    if (!node) return 0;           // height of null = 0
    const lh = check(node.left);
    if (lh === -1) return -1;      // early exit
    const rh = check(node.right);
    if (rh === -1) return -1;
    if (Math.abs(lh - rh) > 1) return -1;   // unbalanced
    return 1 + Math.max(lh, rh);
  }
  return check(root) !== -1;
}
// Time: O(n)   Space: O(h)

Problem 3 — Verify Red-Black tree properties (black-height consistency check):

function verifyRB(root) {
  let valid = true;

  function blackHeight(node) {
    if (!node) return 1;   // NIL sentinel counts as 1 black node
    if (node.color === RED) {
      // Property 4: no two consecutive reds
      if ((node.left  && node.left.color  === RED) ||
          (node.right && node.right.color === RED)) {
        valid = false;
      }
    }
    const lbh = blackHeight(node.left);
    const rbh = blackHeight(node.right);
    if (lbh !== rbh) valid = false;  // Property 5
    return (node.color === BLACK ? 1 : 0) + lbh;
  }

  if (root && root.color !== BLACK) valid = false;  // Property 2
  blackHeight(root);
  return valid;
}
// Time: O(n)   Space: O(h)

Time & Space Complexity Summary

Operation	AVL	Red-Black	Note
Search	O(log n)	O(log n)	AVL slightly faster in practice
Insert	O(log n)	O(log n)	RB fewer rotations
Delete	O(log n)	O(log n)	RB at most 3 rotations
Space per node	O(1) extra	O(1) extra	1 int vs 1 bit
Build from n items	O(n log n)	O(n log n)	—

Tip

For most interview purposes, you will not be asked to implement a full Red-Black tree from scratch. Focus on knowing the five properties, why recolouring works, and when to prefer RB over AVL. AVL rotations are far more likely to be coded live.