Understanding Red‑Black Trees and Related Balanced Tree Structures

Preface

The article introduces the red‑black tree, a widely discussed balanced tree structure, and explains its significance.

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

Definition from Wikipedia

A binary search tree (BST) is a binary tree that satisfies three properties: left subtree values are less than the node, right subtree values are greater than or equal to the node, and both subtrees are themselves BSTs.

Illustration

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 nodes are inserted in sorted order, a BST can degenerate into a linked list, known as a "left‑leaning" or "right‑leaning" tree.

Balanced Trees

A balanced tree ensures that the height difference between any node's subtrees does not exceed one. Common balanced trees include AVL trees, B‑trees (including 2‑3 and 2‑3‑4 trees), and red‑black trees.

AVL Tree

AVL trees are self‑balancing binary search trees where the height difference between left and right subtrees of any node is at most one. They automatically adjust after insertions to maintain balance.

2‑3 Tree

Basic Concept

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), and all leaves share the same depth.

Properties: 1) Satisfies BST properties; 2) Nodes store one or two elements; 3) Nodes have two or three children.

Creation Rules

Insertion involves adding elements to 2‑nodes or handling a solitary 3‑node tree.

2‑3‑4 Tree

Definition

2‑node: two children, one element.

3‑node: three children, one element.

4‑node: four children, one element.

Rules

Rule 1: New nodes are added to the last leaf, not to empty positions. Rule 2: A 4‑node can be split into three 2‑nodes, and the split root merges upward.

Insertion Process

Show the original 2‑3‑4 tree.

Insert a new node (e.g., 17) and merge it according to Rule 1.

Split a 4‑node (e.g., [16,17,18,20]) according to Rule 2.

Re‑balance by merging split roots upward.

Repeat for other 4‑nodes to complete the tree.

This process demonstrates how 2‑3‑4 trees maintain balance during insertions.

B‑Tree

A B‑tree generalizes the concept of multi‑way balanced trees, allowing nodes to have more than two children while keeping all leaves at the same depth. The degree of a B‑tree indicates the maximum number of children per node.

Red‑Black Tree

Overview

A red‑black tree (R‑B Tree) is a special binary search tree where each node is colored red or black, adhering to five properties that guarantee near‑balanced height.

Understanding Red‑Black Trees

Red‑black trees correspond to 2‑3‑4 trees: each black node represents a 2‑node or 3‑node, and red nodes represent the extra elements of a 4‑node.

Each node is either red or black.

The root is black.

All NIL leaves are black.

Red nodes cannot have red children.

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

By treating a red‑black tree as a 2‑3‑4 tree and applying color changes and rotations, we can maintain its balance.

Maintaining Structure

When inserting a new node, rotations (left and right) are used to preserve the five red‑black properties.

Left Rotation

Pivot around a node's right child, making the right child the new subtree root and moving the original node to become the left child of the new root.

Right Rotation

Pivot around a node's left child, making the left child the new subtree root and moving the original node to become the right child of the new root.

Applications

Red‑black trees are widely used to store ordered data with O(log n) operations, such as Java's TreeSet and TreeMap, C++ STL's set and map, and Linux virtual memory management.