Understanding Red-Black Trees and Related Balanced Binary Search Trees

Introduction

This article explains the concept of red‑black trees, a widely used self‑balancing binary search tree, and provides background on related tree structures.

Binary Tree

A binary tree is an ordered tree where each node has at most two children, commonly referred to as the left and right subtrees.

Binary Search Tree

A binary search tree (BST) is a binary tree that satisfies three properties: the left subtree of a node contains only nodes with keys less than the node’s key, the right subtree contains only nodes with keys greater than or equal to the node’s key, and both subtrees are themselves BSTs.

Illustrative Example

Searching for the value 29 proceeds by comparing with the root (41), moving to the left child (20), then to the right child (29), where the target is found.

Degeneration

If keys are inserted in sorted order, a BST can degenerate into a linked list ("left‑leaning" or "right‑leaning"), leading to poor performance.

Balanced Trees

Balanced trees keep the height difference between child subtrees of any node at most one, ensuring O(log n) operations. Examples include AVL trees, 2‑3 trees, 2‑3‑4 trees, and B‑trees.

AVL Tree

AVL trees are self‑balancing BSTs where the height difference of child subtrees never exceeds one.

2‑3 Tree

A 2‑3 tree is a self‑balancing tree where each internal node is either a 2‑node (two children, one data element) or a 3‑node (three children, two data elements); all leaves reside at the same depth.

Properties: (1) Satisfies BST properties; (2) Nodes store one or two elements; (3) Each node has two or three children.

2‑3‑4 Tree

A 2‑3‑4 tree extends the concept: internal nodes may be 2‑nodes, 3‑nodes, or 4‑nodes (four children, three data elements) and remains self‑balancing.

Rule 1: New nodes are added to the rightmost leaf. Rule 2: A 4‑node splits into three 2‑nodes, and the middle key moves up.

B‑Tree

B‑trees generalize these structures; a B‑tree of degree 3 corresponds to a 2‑3 tree, and degree 4 corresponds to a 2‑3‑4 tree.

Red‑Black Tree

Overview

A red‑black tree is a binary search tree where each node is colored red or black, satisfying five properties that guarantee the tree remains approximately balanced.

Key Properties

Each node is either red or black.

The root is black.

All leaves (NIL nodes) are black.

Red nodes cannot have red children.

Every path from a node to its descendant leaves contains the same number of black nodes.

Rotations

To maintain balance after insertions or deletions, left and right rotations are performed.

Left Rotation

Right Rotation

Applications

Red‑black trees are used in many systems to store ordered data efficiently, such as Java’s TreeSet and TreeMap, C++ STL’s set and map, and Linux’s virtual memory management.