Data Structures

Balanced Trees: AVL and Red-Black

Цели урока

  • Understand why a plain BST isn't enough
  • Study AVL and its rotations
  • Get acquainted with Red-Black trees
  • Learn to choose the right structure for the task

Предварительные знания

  • Binary Search Tree
  • Binary Search Tree

In 1962, two Soviet mathematicians solved the problem: how to make sure a tree never degenerates into a list? Their invention - the AVL tree - is still used in databases today.

  • Linux kernel - Red-Black for the scheduler
  • Java TreeMap/TreeSet - Red-Black
  • C++ std::map - Red-Black
  • PostgreSQL - AVL for in-memory indexes

The first self-balancing tree

The weakness of a plain BST on sorted input was solved by the Soviet mathematicians Georgy Adelson-Velsky and Evgenii Landis: in 1962 they described the AVL tree, the first structure that keeps itself balanced through rotations and guarantees O(log n) height. A decade later, in 1972, Rudolf Bayer proposed symmetric binary B-trees, and Leo Guibas and Robert Sedgewick reframed them in 1978 as red-black trees with the node colouring we know today. These ideas left theory for practice long ago: red-black trees sit behind std::map in C++, TreeMap in Java, and the CFS scheduler in the Linux kernel. That is how the logarithmic-height guarantee of this lesson runs inside code we use every day.

The Imbalance Problem

A BST promises O(log n), but only for **balanced** trees.

**Worst-case BST = linked list.** Search in O(n) - no better than an array!

What is the search complexity in a degenerate BST of n elements?

AVL Tree: Strict Balance

**AVL tree** (Adelson-Velsky and Landis, 1962) - the first self-balancing BST.

**AVL property:** for every node, the heights of the left and right subtrees differ by **at most 1**.

An AVL tree allows subtree height differences of:

Rotations: Restoring Balance

When balance is violated, AVL performs **rotations** - local rearrangements of nodes.

Right rotation (Left-Left case)

4 imbalance cases

CaseImbalanceFix
Left-Leftz.left.leftSingle right rotation
Right-Rightz.right.rightSingle left rotation
Left-Rightz.left.rightLeft then right rotation
Right-Leftz.right.leftRight then left rotation

How many operations are needed to rebalance after an insertion in an AVL tree?

Red-Black Tree: Relaxed Balance

A **Red-Black Tree** is a more flexible self-balancing tree.

**Red-Black rules:**

  1. Every node is either red or black
  2. The root is always black
  3. Leaves (NIL) are black
  4. A red node cannot have a red child
  5. All paths from a node to its leaf descendants contain the same number of black nodes

**Guarantee:** Red-Black height ≤ 2·log₂(n+1). Less strict than AVL, but easier to maintain.

Which rule does a red node with a red child violate?

AVL vs Red-Black: What to Choose?

PropertyAVLRed-Black
Balance strictnessHigh (diff ≤ 1)Moderate (≤ 2x)
SearchSlightly fasterSlightly slower
Insert/deleteMore rotationsFewer rotations
UsageRead-heavy workloadsWrite-heavy workloads

**Java TreeMap, C++ std::map, Linux kernel** use Red-Black. **Read-heavy databases** prefer AVL.

**In practice:** both structures give O(log n). The difference is in constants - matters only for high-load systems.

For an application with frequent insertions and rare lookups, the better choice is:

Summary

  • AVL: strict balance, height difference ≤ 1
  • Red-Black: softer balance, fewer rotations
  • Both guarantee O(log n) for all operations
  • AVL → reads, Red-Black → writes

Next Topics

From balanced trees to specialized structures.

  • Heap — Another kind of tree for priorities
  • Trie — A tree for strings

Связанные уроки

  • ds-11-bst — Balanced trees extend BST with self-balancing operations
  • ds-13-trie — Trie is another specialised tree for string keys
  • ds-23-btree — B-tree generalises balanced BST for disk-based storage
  • ds-06-hash-intro — Both support an O(log n) ordered map; hash is O(1) but unordered
  • db-09-indexes-btree
Balanced Trees: AVL and Red-Black

0

1

Sign In