Red-Black Tree

A red-black tree is a self-balancing binary search tree where each node has a color (red or black), and rules are followed to guarantee logarithmic tree height.

Rules (Invariants)

Node Structure

class RBNode:
    def __init__(self, key):
        self.key   = key
        self.color = "RED"      # new nodes are always red
        self.left  = None       # NIL leaf
        self.right = None
        self.parent = None

Visualization

Operation Complexity

Tree height ≤ 2 · log₂(n+1) — guaranteed ceiling.

Insertion Algorithm

def insert(self, key):
    # 1. Standard BST insertion (new node is RED)
    node = RBNode(key)
    self._bst_insert(node)

    # 2. Restore invariants
    self._fix_insert(node)

def _fix_insert(self, z):
    while z.parent and z.parent.color == "RED":
        if z.parent == z.parent.parent.left:
            uncle = z.parent.parent.right

            if uncle and uncle.color == "RED":
                # Case 1: uncle is red → recoloring
                z.parent.color         = "BLACK"
                uncle.color            = "BLACK"
                z.parent.parent.color  = "RED"
                z = z.parent.parent
            else:
                if z == z.parent.right:
                    # Case 2: node is right child → left rotation
                    z = z.parent
                    self._rotate_left(z)
                # Case 3: node is left child → right rotation
                z.parent.color        = "BLACK"
                z.parent.parent.color = "RED"
                self._rotate_right(z.parent.parent)
        else:
            # Symmetric cases (right side)
            ...

    self.root.color = "BLACK"   # rule 2

Rotations

Left Rotation (x):          Right Rotation (y):

    x                               y
   / \          →                  / \
  A   y                           x   C
     / \                         / \
    B   C                       A   B

def _rotate_left(self, x):
    y = x.right
    x.right = y.left
    if y.left:
        y.left.parent = x
    y.parent = x.parent
    if not x.parent:
        self.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    y.left = x
    x.parent = y

Comparison with Other Trees

Real-World Applications

• 🔴 Linux Kernel — Completely Fair Scheduler (CFS)
• 🔴 Java — TreeMap, TreeSet, HashMap (on collisions)
• 🔴 C++ STL — std::map, std::set
• 🔴 Nginx — event timers
• 🔴 PostgreSQL — internal memory structures

💡 Tip: If you need to use an RB-Tree in DataPlayer queries, such structures are already built into PostgreSQL and MySQL indexes — you don't need to implement them manually.

Searching in a Red-Black Tree

Search Algorithm

Searching in an RB-Tree is identical to searching in a standard BST — coloring is completely ignored:

def search(node, key):
    if node is NIL or node.key == key:
        return node          # found or reached a leaf

    if key < node.key:
        return search(node.left, key)   # go left
    else:
        return search(node.right, key)  # go right

Main Question: Does Coloring Speed Up Searching?

Short Answer: No, not directly

The node color is not checked during search and does not affect the direction of traversal.

Then Why Colors?

Coloring is an indirect mechanism: it ensures tree balance during insertions and deletions, and balance guarantees fast searching.

Colors → adherence to invariants
       → tree remains balanced
       → height h = O(log n)
       → search runs in O(log n)

How Invariants Limit Height

Rules 4 and 5 together lead to a strict height limit:

The height of an RB-Tree does not exceed 2 · log₂(n+1)

Why this is so:

• Rule 5 → all paths to NIL contain the same number of black nodes (black-height = bh)
• Rule 4 → between two black nodes, there can be at most one red node
• Therefore, the longest path (black-red-black-red-...) is at most twice as long as the shortest path (all black)
• Hence: h ≤ 2 · bh ≤ 2 · log₂(n+1)

{
  "title": { "text": "Maximum Tree Height vs Number of Nodes", "left": "center" },
  "tooltip": { "trigger": "axis" },
  "legend": { "data": ["Unbalanced BST (worst case)", "Red-Black Tree (2·log₂n)", "AVL Tree (1.44·log₂n)"], "bottom": 0 },
  "xAxis": {
    "type": "category",
    "name": "n (nodes)",
    "data": ["1", "10", "50", "100", "500", "1000", "10000", "100000"]
  },
  "yAxis": { "type": "value", "name": "Height" },
  "series": [
    {
      "name": "Unbalanced BST (worst case)",
      "type": "line",
      "data": [1, 10, 50, 100, 500, 1000, 10000, 100000],
      "lineStyle": { "color": "#e74c3c" }
    },
    {
      "name": "Red-Black Tree (2·log₂n)",
      "type": "line",
      "data": [0, 7, 11, 13, 18, 20, 27, 34],
      "lineStyle": { "color": "#e67e22" }
    },
    {
      "name": "AVL Tree (1.44·log₂n)",
      "type": "line",
      "data": [0, 5, 8, 10, 13, 14, 19, 24],
      "lineStyle": { "color": "#2ecc71" }
    }
  ]
}

AVL vs RB-Tree: Search

In practice, the search speed difference between AVL and RB is minimal and often eclipsed by cache effects and implementation details. Therefore, RB-trees are more commonly chosen as a universal structure — they are faster for writes without significantly sacrificing read performance.

Summary

• Search in an RB-tree is standard BST search; colors are ignored.
• Coloring is needed not for search, but to maintain balance during modifications.
• Balance guarantees O(log n) height → search is always O(log n) even in the worst case.
• This is the main advantage over standard BST, which degrades to O(n) on sorted data.