C Mastery / Balanced Trees: AVL and Red-Black
Part 8 — Data Structures and Algorithms in C

Balanced Trees: AVL and Red-Black

This chapter covers self-balancing binary search trees: AVL trees and red-black trees. Both maintain O(log n) worst-case height.

Why This Matters

A plain BST degrades to O(n) on sorted input. Balanced trees guarantee O(log n) search/insert/delete regardless of input order, which is essential for ordered maps/sets in production systems (databases, kernels, runtimes).

Prerequisites

Core Concept

Both trees keep height balanced via rotations after insert/delete:

differs by at most 1. It rebalances with single/double rotations.

guaranteeing height ≤ 2 log₂(n+1). Fewer rotations than AVL.

AVL Tree

typedef struct Node {
    int value;
    int height;
    struct Node *left;
    struct Node *right;
} Node;

Balance factor = height(left) - height(right). When a node's factor is outside [-1, 1], rotate.

Rotations

    y                 x
   / \               / \
  x   C   ---->     A   y
 / \                   / \
A   B                 B   C

Left and right rotations restore balance; left-right/right-left cases need two rotations.

Red-Black Tree

Each node has a color (red/black). The invariants:

1. Every node is red or black. 2. The root is black. 3. No two red nodes are adjacent. 4. Every path from a node to its descendant NULL leaves has the same number of black nodes.

Insert/delete fix violations with rotations and recoloring.

Examples

AVL height and balance

static int height(Node *n) { return n ? n->height : 0; }

static int balance(Node *n) { return height(n->left) - height(n->right); }

static Node *rotate_right(Node *y)
{
    Node *x = y->left;
    Node *T2 = x->right;
    x->right = y;
    y->left = T2;
    y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));
    x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));
    return x;
}

AVL insert (skeleton)

Node *avl_insert(Node *n, int value)
{
    if (!n) return new_node(value);
    if (value < n->value) n->left = avl_insert(n->left, value);
    else if (value > n->value) n->right = avl_insert(n->right, value);
    else return n;   /* no duplicates */

    n->height = 1 + max(height(n->left), height(n->right));
    int b = balance(n);

    if (b > 1 && value < n->left->value)   return rotate_right(n);
    if (b < -1 && value > n->right->value) return rotate_left(n);
    if (b > 1 && value > n->left->value)  { n->left = rotate_left(n->left); return rotate_right(n); }
    if (b < -1 && value < n->right->value){ n->right = rotate_right(n->right); return rotate_left(n); }
    return n;
}

How It Works

Rotations restructure a small local subtree without violating the BST ordering, reducing height. AVL rebalances immediately and strictly; red-black rebalances lazily with colors, doing fewer rotations per insert.

Variations

AVL vs. red-black

Splay trees, B-trees

Other balanced structures trade different properties; B-trees are the basis of databases and filesystems.

Common Mistakes

Undefined Behavior

Portability

Under the Hood

Rotations are pointer rewrites; the compiler keeps the hot nodes in cache. Balanced trees still chase pointers, so they are less cache-friendly than arrays, but they guarantee logarithmic behavior.

Practical Usage

Exercises

1. Implement AVL insert with all four rotation cases. 2. Implement AVL delete (the hardest part of the chapter). 3. Implement red-black insert with recoloring/rotations. 4. Verify height stays balanced after many random inserts.

Deep Challenge

Implement AVL delete, explaining each rebalance case and why delete requires more rotations than insert. Then test with a random sequence and verify the AVL invariant after every step.

References

Verification

verified.`

Progress

Concept checkboxes

Mastery levels

ConceptCurrent level (0–8)Target level
c.ds.avl06
c.ds.redblack06
← PrevNext →