Red-Black Tree

Introduction

A Red-Black Tree is a type of self-balancing binary search tree (BST). It guarantees that the height of the tree remains logarithmic with respect to the number of elements, ensuring efficient search, insertion, and deletion operations — all in O(log n) time.

What makes a Red-Black Tree special is its use of color-based properties (red or black) to enforce balance, without requiring as many rotations as stricter trees like AVL Trees. It is widely used in real-world systems, including the Linux kernel, Java’s TreeMap, and C++ STL’s std::map.

Why Red-Black Trees?

In unbalanced BSTs, the tree may degrade into a linear chain (like a linked list), making operations O(n). Red-Black Trees maintain balance automatically by enforcing specific coloring and structural rules, which limit the maximum tree height to 2 × log₂(n + 1).

This balance ensures:

Efficient worst-case performance
Fewer rotations than AVL Trees
Fast rebalancing for large-scale systems

Red-Black Tree Properties

A Red-Black Tree satisfies the following five key properties:

Each node is either red or black.
The root is always black.
All leaves (null children) are considered black.
If a node is red, then both its children must be black (no two red nodes can be adjacent).
Every path from a node to its descendant null nodes contains the same number of black nodes.

These rules guarantee a balanced structure and restrict how the tree grows.

Node Structure

Each node typically contains: (Python)

class Node:
    def __init__(self, key, color="RED"):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None
        self.color = color  # RED or BLACK

Insertion in Red-Black Tree

Step-by-Step Overview

Insert the new node like in a regular BST (as a red node).
Fix any violations of the Red-Black Tree properties via rotations and recoloring.

Insertion Fix Cases

Assume the new node’s parent is red (which violates property 4). There are three major cases:

Case 1 (Uncle is red): Recolor parent and uncle black, grandparent red, move up the tree.
Case 2 (Uncle is black, triangle configuration): Perform rotation to make it a straight line.
Case 3 (Uncle is black, straight line): Recolor and perform rotation.

Python Example (Simplified Skeleton)

Due to complexity, a full implementation is large, but a simplified insertion pattern is:

def insert(root, key):
    new_node = Node(key)
    bst_insert(root, new_node)
    fix_violations(root, new_node)

Actual balancing involves left/right rotations and recoloring.

Rotations

Left Rotation

     x               y
      \             /
       y    →      x

def left_rotate(root, x):
    y = x.right
    x.right = y.left
    if y.left:
        y.left.parent = x
    y.parent = x.parent
    if x.parent is None:
        root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    y.left = x
    x.parent = y
    return root

Right Rotation is symmetric.

Deletion in Red-Black Tree

Deletion is more complex than insertion:

Delete the node like a BST.
If the deleted node or the node replacing it is black, you must fix the double black violation.

Fixing involves:

Recoloring
Rotations
Propagating fixes up the tree

This process ensures that the number of black nodes on all paths remains consistent.

Red-Black Tree vs AVL Tree

Feature	Red-Black Tree	AVL Tree
Balance Strictness	Looser (more flexible)	Stricter (height difference ≤ 1)
Rotations Frequency	Fewer	More frequent
Lookup Performance	Slightly worse (but still O(log n))	Faster lookups
Insertion/Deletion	Faster	Slightly slower
Use Case	Databases, OS kernels	Read-heavy systems

Red-Black Tree Use Cases

Operating Systems: Linux process scheduler (completely fair scheduling)
Compilers/Interpreters: Symbol tables
Java Collections: TreeMap, TreeSet
C++ STL: std::map, std::set
Databases: Index trees (e.g., for in-memory storage)

Performance Analysis

Operation	Time Complexity
Search	O(log n)
Insert	O(log n)
Delete	O(log n)
Space	O(n)

Logarithmic time is guaranteed due to strict balancing.
At most 2 rotations per insertion or deletion.

Visualization Example

Initial Tree:

   10(B)

Insert 18:

   10(B)
       \
      18(R)

Insert 7:

     10(B)
     /   \
  7(R)  18(R)

Now both children of root are red → Recolor:

     10(R)
     /   \
  7(B)  18(B)

If violations propagate, more rotations and recoloring are applied recursively.

Advantages of Red-Black Trees

Guaranteed logarithmic performance
Fewer rotations than AVL
Efficient for frequent inserts/deletes
Well-supported in language libraries

Drawbacks

More complex to implement than BST or AVL
Not as tightly balanced as AVL (slightly slower lookups)
Harder to visualize and debug manually

Python Tip: Use `sortedcontainers`

If you need a red-black-tree-like structure in Python, sortedcontainers provides:

pip install sortedcontainers

from sortedcontainers import SortedDict
d = SortedDict()
d[5] = "A"
d[1] = "B"
print(d)  # Keys are kept sorted

Internally uses a balanced tree similar to red-black trees.

Summary

A Red-Black Tree is a self-balancing binary search tree that uses color properties and rotations to maintain balance and ensure operations run in O(log n) time. It is especially favored in real-world applications for its fast insertions and deletions and predictable performance under high load.

Though more complex to implement than basic BSTs or even AVL trees, Red-Black Trees are a practical choice for performance-critical systems like databases, file systems, and runtime libraries.