Red-Black Trees: A Deep Dive

CSE310 Data Structures and Algorithms: Recitation 11/17

w/ CLRS pseudocode and C++ implementations

Motivation - Why Red-Black Trees?

Problem: Unbalanced Binary Search Trees can degrade to O(n) height, making operations inefficient.

Solution: Red-Black Trees guarantee O(log n) height for all operations through color-based balancing constraints.

BST (Unbalanced)

Height: O(n)

Insert: O(n)

Delete: O(n)

⚠️ Worst Case

AVL Tree

Height: O(log n)

Insert: O(log n) rotations

Delete: O(log n) rotations

More rotations

RB Tree

Height: O(log n)

Insert: O(1) rotations

Delete: O(1) rotations

✓ Optimal

                Real-world uses: Java TreeMap/TreeSet, C++ std::map/set, Linux kernel CFS scheduler
            

Key Insight: Colors enforce balance constraints that guarantee the tree never becomes too unbalanced, ensuring O(log n) operations.

What are Red-Black Trees?

A Binary Search Tree where each node is colored either RED or BLACK. These colors enforce constraints that automatically maintain balance.

Key Insight: Unlike unbalanced BSTs that degrade to O(n), RB trees guarantee O(log n) operations

Red-Black Tree Definition

A Red-Black Tree is a Binary Search Tree with an additional color attribute (RED or BLACK) on each node that enforces specific structural properties. These properties guarantee the tree maintains O(log n) height.

Formal Definition

A red-black tree is a binary search tree where each node contains an extra bit for denoting the color (red or black), used to ensure the tree remains approximately balanced during insertions and deletions.

Historical Note: Red-Black trees were invented by Rudolf Bayer in 1972 and formalized by Leonidas J. Guibas and Robert Sedgewick in 1978. The name comes from the two colors used to mark nodes.

The 5 Red-Black Tree Properties (Detailed)

Property 1: Every node is colored RED or BLACK
Property 2: The root is always BLACK
Property 3: All leaves (NIL nodes) are BLACK
Property 4: If a node is RED, then both its children are BLACK
→ No two consecutive RED nodes allowed on any path
Property 5: For each node, all simple paths from it to descendant leaves contain the same number of BLACK nodes
→ This is the "black-height" property, denoted bh(x)

Why These Properties Guarantee O(log n)?

Mathematical Proof:

Lemma: Subtree Size by Black-Height

A subtree rooted at any node x contains at least 2^bh(x) - 1 internal nodes, where bh(x) is the black-height of x.

Proof: By induction on height of x.

Property 4 prevents chains: No path can have more than h/2 red nodes (since reds can't be consecutive)
Property 5 ensures balance: All paths have the same number of black nodes
Result: Longest path ≤ 2 × shortest path
Corollary: For a tree with n nodes, height h ≤ 2·lg(n+1)

                Therefore: Search, Insert, and Delete all run in O(log n) time!

                The tree height is guaranteed to be logarithmic, ensuring efficient operations.

Source: Cormen, Leiserson, Rivest, Stein - "Introduction to Algorithms" (CLRS), Chapter 13

Node Structure in C++

Complete C++ struct definition for a Red-Black Tree node:

C++ Node Structure

struct Node {
    int key;                    // Data/key value
    Node* parent;               // Pointer to parent node
    Node* left;                 // Pointer to left child
    Node* right;                // Pointer to right child
    int color;                  // RED (1) or BLACK (0)
    
    // Constructor
    Node(int k) : key(k), parent(nullptr), 
                  left(nullptr), right(nullptr), 
                  color(1) {}  // New nodes are RED by default
};

enum Color { BLACK = 0, RED = 1 };

Why we need a parent pointer:

Required for rotations - must update parent's child pointers
Essential for fixup operations that walk up the tree
Allows traversal in both directions

Reference: Programiz - Red-Black Tree Data Structure

Sentinel NIL Node

Problem: Boundary conditions with null pointers make code complex and error-prone.

Solution: Use a single sentinel T.nil to represent all NULL values.

Sentinel Node Properties

All leaf pointers point to T.nil (instead of nullptr)
Root's parent points to T.nil
T.nil is colored BLACK (satisfies Property 3)
Single sentinel shared by all leaves

C++ Implementation with Sentinel

class RedBlackTree {
private:
    Node* root;
    Node* TNULL;  // The sentinel NIL node
    
public:
    RedBlackTree() {
        TNULL = new Node(0);
        TNULL->color = BLACK;
        TNULL->left = nullptr;
        TNULL->right = nullptr;
        TNULL->parent = nullptr;
        root = TNULL;  // Empty tree: root points to TNULL
    }
};

                Benefits:

                • Simplifies code - avoids null checks in many places

                • Memory efficient - one sentinel vs many null nodes

                • Uniform treatment of leaves

Complete Tree Class Structure

Full C++ class declaration with all methods:

Complete RedBlackTree Class

class RedBlackTree {
private:
    Node* root;
    Node* TNULL;  // Sentinel NIL node
    
    // Private helper methods
    void leftRotate(Node* x);
    void rightRotate(Node* x);
    void insertFix(Node* k);
    void deleteFix(Node* x);
    void rbTransplant(Node* u, Node* v);
    Node* minimum(Node* node);
    
public:
    RedBlackTree();
    void insert(int key);
    void deleteNode(int key);
    Node* search(int key);
    void inorderTraversal();
};

Design Pattern: Private helper methods (rotations, fixups) are internal operations. Public methods provide the interface for insertion, deletion, and search.

Reference: Programiz - Red-Black Tree Implementation

Why These Properties Matter

Property 4 prevents long chains - no chain of 3 nodes is possible without violating the RB constraints. Property 5 ensures the tree doesn't become skewed.

Together, they guarantee height ≤ 2·lg(n+1), giving us O(log n) operations

Mathematical Guarantee

• Shortest path from root to leaf: Contains only black nodes

• Longest path from root to leaf: Alternates red and black nodes

• Since all paths have same # of black nodes (Property 5), longest path ≤ 2 × shortest path

• Result: The tree is approximately balanced with height ≤ 2·lg(n+1)

What are Rotations?

Definition

Rotation is a local restructuring operation that maintains the BST property while changing the tree structure.

Purpose: Used to fix RB-tree violations after insertion/deletion
Key Property: BST order is maintained; only pointers change
Time Complexity: O(1) - constant number of pointer changes
Types: Left rotation and right rotation (mirror operations)

Left Rotation

→

Left Rotation on x: right child y moves up, y's left subtree β becomes x's right subtree

Right Rotation

Right Rotation on x: left child y moves up, y's right subtree becomes x's left subtree (mirror of left rotation)

Left Rotation - Detailed

CLRS Pseudocode

LEFT-ROTATE(T, x)
  y = x.right
  x.right = y.left
  if y.left ≠ T.nil
    y.left.p = x
  y.p = x.p
  if x.p == T.nil
    T.root = y
  elseif x == x.p.left
    x.p.left = y
  else
    x.p.right = y
  y.left = x
  x.p = y

C++ Implementation

void leftRotate(Node* x) {
  Node* y = x->right;
  x->right = y->left;
  
  if (y->left != TNULL)
    y->left->parent = x;
  
  y->parent = x->parent;
  
  if (x->parent == nullptr)
    root = y;
  else if (x == x->parent->left)
    x->parent->left = y;
  else
    x->parent->right = y;
  
  y->left = x;
  x->parent = y;
}

Step-by-step: y becomes x's right child → Move y's left subtree to x's right → Link y to x's parent → x becomes y's left child

Right Rotation - Detailed

Right rotation is the mirror image of left rotation (swap left/right):

CLRS Pseudocode

RIGHT-ROTATE(T, x)
  y = x.left
  x.left = y.right
  if y.right ≠ T.nil
    y.right.p = x
  y.p = x.p
  if x.p == T.nil
    T.root = y
  elseif x == x.p.right
    x.p.right = y
  else
    x.p.left = y
  y.right = x
  x.p = y

C++ Implementation

void rightRotate(Node* x) {
  Node* y = x->left;
  x->left = y->right;
  
  if (y->right != TNULL)
    y->right->parent = x;
  
  y->parent = x->parent;
  
  if (x->parent == nullptr)
    root = y;
  else if (x == x->parent->right)
    x->parent->right = y;
  else
    x->parent->left = y;
  
  y->right = x;
  x->parent = y;
}

Reference: CLRS Chapter 13.2 - Rotations

Rotation Examples

Concrete Example: Left rotation on specific tree

Left Rotation Example

→

                Observe: BST property maintained! Inorder: α, 5, β, 8, γ (same before and after)
            

Insertion Overview

Always insert as RED because this is less likely to violate property 5 (black height). Only recolor/rotate as needed.

Insert node as RED (like standard BST insertion)
Check for violations (red node with red parent)
Fix violations using recoloring and rotations

                Why insert as RED?

                Inserting a red node doesn't change black heights on any path. We only have a problem if the parent is also red.

RB-INSERT Pseudocode (CLRS)

CLRS Pseudocode

RB-INSERT(T, z)
  y = T.nil
  x = T.root
  while x ≠ T.nil
    y = x
    if z.key < x.key
      x = x.left
    else
      x = x.right
  
  z.p = y
  if y == T.nil
    T.root = z
  elseif z.key < y.key
    y.left = z
  else
    y.right = z
  
  z.left = T.nil
  z.right = T.nil
  z.color = RED
  RB-INSERT-FIXUP(T, z)

C++ Implementation

void insert(int key) {
  Node* node = new Node(key);
  node->left = TNULL;
  node->right = TNULL;
  node->color = RED;
  
  Node* y = nullptr;
  Node* x = root;
  
  while (x != TNULL) {
    y = x;
    if (node->key < x->key)
      x = x->left;
    else
      x = x->right;
  }
  
  node->parent = y;
  if (y == nullptr)
    root = node;
  else if (node->key < y->key)
    y->left = node;
  else
    y->right = node;
  
  insertFix(node);
}

Source: CLRS Chapter 13.3 - Insertion

RB-INSERT-FIXUP Overview

Problem: New red node might have red parent (violates property 4)

Solution: Walk up the tree fixing violations

Key Variables in Fixup

z: current node being fixed (always red at start of iteration)
z.p: parent of z
z.p.p: grandparent of z
y: uncle of z (sibling of z.p)

Loop Invariant: At the start of each iteration, z is RED and z.p is RED (violation exists). We maintain all other RB properties.

Insertion - Case Analysis Setup

Three main cases based on uncle's color and node position:

Case 1

Uncle is RED

Solution: Recolor

Case 2

Uncle BLACK, Triangle

Solution: Rotate to line

Case 3

Uncle BLACK, Line

Solution: Rotate & recolor

Processing: The algorithm processes from z upward until:
• We reach the root, OR
• Case 3 terminates the loop (permanent fix)

                Each case either fixes the violation or reduces it to another case. Case 1 may repeat O(log n) times. Cases 2 and 3 are terminal (at most one rotation each).
            

Insertion Case 1: Uncle is RED

Scenario

New red node has red parent and RED uncle

Solution

1 Recolor parent → BLACK

2 Recolor uncle → BLACK

3 Recolor grandparent → RED

4 Check grandparent for violations

This is the simplest case. We just change colors. Then check grandparent for violations.

→

Insertion Case 2: Uncle is BLACK (Triangle)

Scenario

New red node, red parent, BLACK uncle. Node and parent form a triangle with grandparent.

Solution

If node is right child of left-parent (or left child of right-parent), rotate to straighten the line

This converts the problem to Case 3. We perform a rotation to transform the triangle into a line configuration.

→

Insertion Case 3: Uncle is BLACK (Line)

Scenario

New red node, red parent, BLACK uncle. All form a straight line.

Solution

1 Rotate parent up to grandparent position

2 Recolor: parent → BLACK, grandparent → RED

This fixes the violation permanently. Parent moves up to grandparent position and becomes black.

→

Complete RB-INSERT-FIXUP Pseudocode

CLRS Complete Algorithm

RB-INSERT-FIXUP(T, z)
  while z.p.color == RED
    if z.p == z.p.p.left
      y = z.p.p.right                    // y is uncle
      
      if y.color == RED                 // Case 1
        z.p.color = BLACK
        y.color = BLACK
        z.p.p.color = RED
        z = z.p.p
      else
        if z == z.p.right                // Case 2
          z = z.p
          LEFT-ROTATE(T, z)
        
        z.p.color = BLACK                // Case 3
        z.p.p.color = RED
        RIGHT-ROTATE(T, z.p.p)
    
    else                                 // Mirror cases (z.p is right child)
      y = z.p.p.left
      
      if y.color == RED
        z.p.color = BLACK
        y.color = BLACK
        z.p.p.color = RED
        z = z.p.p
      else
        if z == z.p.left
          z = z.p
          RIGHT-ROTATE(T, z)
        
        z.p.color = BLACK
        z.p.p.color = RED
        LEFT-ROTATE(T, z.p.p)
  
  T.root.color = BLACK

Source: CLRS Chapter 13.3 - Complete algorithm with all cases

Insertion Example Part 1

Start with empty tree, insert 7:

Initial

Insert 7

Result: Node 7 becomes root, colored BLACK (Property 2)
Tree: [7(B)] where B = BLACK

Insertion Example Part 2

Insert 3 (left of 7):

Analysis:
• Node 3 inserted as RED, left child of 7
• No violation: Parent 7 is BLACK
• No fixup needed!
Tree: [7(B) with left child 3(R)]

Insertion Example Part 3

Insert 18 (right of 7):

Analysis:
• Node 18 inserted as RED, right child of 7
• No violation: Parent 7 is BLACK
• Perfect balance with two RED children!
Tree: Balanced [7(B), 3(R), 18(R)]

Insertion Example Part 4 - With Fixup

Insert 10 (left of 18, triggers Case 1):

                Case 1 Applied: Uncle 3 is RED → Recolor parent 18 and uncle 3 to BLACK, grandparent 7 to RED. Since 7 is root, make it BLACK. Done!
            

Key Insights on Insertion

Time complexity: O(log n) - at most O(log n) nodes visited in fixup loop
Maximum rotations: At most 2 (one in Case 2, one in Case 3)
Case progression: Case 2 always leads to Case 3, which terminates
Why insert RED: Black-height property would be much harder to restore

Complexity Analysis

Each iteration: Either stops (Cases 2-3) or moves z up 2 levels (Case 1)

Maximum iterations: O(log n) because tree height is O(log n)

Total time: O(log n) iterations × O(1) per iteration = O(log n)

Reference: VisualGo - Red-Black Tree Visualization

Insertion: Complete Example

Watch how the tree self-balances as we insert values: 7, 3, 18, 10, 22, 8

Insert 7

Insert 3

Insert 18

Insert 10

                Notice how colors change to maintain properties. Each insertion may trigger case handling, but the tree remains balanced!
            

Deletion Overview

Deletion is more complex than insertion. When we delete a node, we might violate the black-height property.

Perform standard BST deletion
If deleted node was BLACK, we have a problem
Handle the "Double Black" situation
Fix violations using rotations and recoloring

The Double Black Concept

When a black node is deleted, one path loses a black node. We mark the replacement node as "double black" - carrying an extra black to maintain the count.

We propagate this double-black mark up the tree until we can eliminate it through recoloring and rotations.

Node Transplant Operation

Helper function used extensively in deletion:

CLRS Pseudocode

RB-TRANSPLANT(T, u, v)
  if u.p == T.nil
    T.root = v
  elseif u == u.p.left
    u.p.left = v
  else
    u.p.right = v
  v.p = u.p

C++ Implementation

void rbTransplant(Node* u, Node* v) {
  if (u->parent == nullptr)
    root = v;
  else if (u == u->parent->left)
    u->parent->left = v;
  else
    u->parent->right = v;
  
  v->parent = u->parent;
}

Purpose: Replace subtree rooted at u with subtree rooted at v
Note: Unlike BST transplant, always updates v.parent (even if v is T.nil)

RB-DELETE Pseudocode (Part 1)

CLRS RB-DELETE Algorithm

RB-DELETE(T, z)
  y = z
  y-original-color = y.color
  
  if z.left == T.nil
    x = z.right
    RB-TRANSPLANT(T, z, z.right)
  
  elseif z.right == T.nil
    x = z.left
    RB-TRANSPLANT(T, z, z.left)
  
  else
    y = TREE-MINIMUM(z.right)
    y-original-color = y.color
    x = y.right
    
    if y.p == z
      x.p = y
    else
      RB-TRANSPLANT(T, y, y.right)
      y.right = z.right
      y.right.p = y
    
    RB-TRANSPLANT(T, z, y)
    y.left = z.left
    y.left.p = y
    y.color = z.color
  
  if y-original-color == BLACK
    RB-DELETE-FIXUP(T, x)

Source: CLRS Chapter 13.4 - Deletion

Understanding Double-Black

The Core Problem: When we delete a BLACK node, we lose one black on some paths.

The Double-Black Concept

The property violation: Some paths now have fewer black nodes (violates Property 5).

Solution: Mark the replacement node as "double-black" - conceptually carrying an extra black.

This extra black is not a real color, but a marker that we need to redistribute or eliminate.

Goal of RB-DELETE-FIXUP: Move this double-black up the tree until:
1. It reaches the root (just remove the extra black), OR
2. It combines with a RED node (turn RED+black to BLACK), OR
3. We redistribute blacks through rotations and recoloring

RB-DELETE-FIXUP Overview

Process: While x is not root and x is BLACK, apply cases based on sibling's configuration.

Invariant: x has an extra black (double-black marker)
Strategy: If sibling is RED, convert to case where sibling is BLACK
Four Cases: Based on sibling's color and its children's colors
Termination: Either x becomes root or we eliminate the extra black

                Like insertion, deletion has symmetric cases for left/right. We'll show cases for when x is a left child; mirror for right child.
            

Deletion Case 1 - RED Sibling

Setup

Sibling w of x is RED (x's parent must be BLACK)

Solution

1 Recolor: w → BLACK, x.p → RED

2 Rotate sibling w up (LEFT-ROTATE on x.p)

3 Update w to be new sibling

Effect: Converts to case where sibling is BLACK

CLRS Pseudocode (Case 1)

if w.color == RED
  w.color = BLACK
  x.p.color = RED
  LEFT-ROTATE(T, x.p)
  w = x.p.right

Deletion Case 2 - BLACK Sibling, Both Children BLACK

Setup

Sibling w is BLACK, both w.left and w.right are BLACK

Solution

1 Recolor sibling w to RED

2 Move double-black up to parent: x = x.p

Effect: Parent now carries the extra black; continue loop

CLRS Pseudocode (Case 2)

if w.left.color == BLACK and w.right.color == BLACK
  w.color = RED
  x = x.p

This is the only case that propagates the double-black upward. May repeat O(log n) times.

Deletion Case 3 - BLACK Sibling, Near Child RED

Setup

Sibling w is BLACK, w's near child (left) is RED, w's far child (right) is BLACK

Solution

1 Recolor: w.left → BLACK, w → RED

2 RIGHT-ROTATE on w

3 Update w to new sibling

Effect: Converts to Case 4

CLRS Pseudocode (Case 3)

if w.right.color == BLACK
  w.left.color = BLACK
  w.color = RED
  RIGHT-ROTATE(T, w)
  w = x.p.right

Deletion Case 4 - BLACK Sibling, Far Child RED

Setup

Sibling w is BLACK, w's far child (right) is RED

Solution

1 Recolor: w → x.p.color, x.p → BLACK, w.right → BLACK

2 LEFT-ROTATE on x.p

3 Set x = T.root to terminate loop

Effect: Eliminates the double-black permanently!

CLRS Pseudocode (Case 4)

w.color = x.p.color
x.p.color = BLACK
w.right.color = BLACK
LEFT-ROTATE(T, x.p)
x = T.root  // Terminate loop

                This is the terminal case! After Case 4, the double-black is eliminated and the loop exits.
            

Complete RB-DELETE-FIXUP Pseudocode

CLRS Complete Algorithm

RB-DELETE-FIXUP(T, x)
  while x ≠ T.root and x.color == BLACK
    if x == x.p.left
      w = x.p.right
      
      if w.color == RED              // Case 1
        w.color = BLACK
        x.p.color = RED
        LEFT-ROTATE(T, x.p)
        w = x.p.right
      
      if w.left.color == BLACK and w.right.color == BLACK    // Case 2
        w.color = RED
        x = x.p
      else
        if w.right.color == BLACK    // Case 3
          w.left.color = BLACK
          w.color = RED
          RIGHT-ROTATE(T, w)
          w = x.p.right
        
        w.color = x.p.color          // Case 4
        x.p.color = BLACK
        w.right.color = BLACK
        LEFT-ROTATE(T, x.p)
        x = T.root
    
    else                             // Mirror cases (x is right child)
      [symmetric with left/right swapped]
  
  x.color = BLACK

Source: CLRS Chapter 13.4 - Complete deletion fixup with all 4 cases

Deletion Example - Complete Walkthrough

Example: Delete node 13 from a valid RB tree

Analysis: Node 13 deleted, successor 15 promoted. Black node deleted, but after fixup the RB properties are still satisfied.

Time Complexity Analysis

Operation	Time Complexity	Detailed Explanation
Search	O(log n)	Height is O(log n), standard BST search
Insertion	O(log n)	BST insert O(log n) + fixup O(log n), at most 2 rotations
Deletion	O(log n)	BST delete O(log n) + fixup O(log n), at most 3 rotations
Space	O(n)	One extra bit per node for color + parent pointer

Height Guarantee Proof

Theorem: A red-black tree with n internal nodes has height h ≤ 2·lg(n+1)

Proof sketch:

Let bh = black-height of root
By Property 5, all paths have bh black nodes
By Property 4, at most h/2 red nodes on any path
Therefore: bh ≥ h/2, so h ≤ 2·bh ≤ 2·lg(n+1)

Why RB-Trees over AVL?

RB Trees

Balance: h ≤ 2·lg(n+1)

Insert rotations: ≤2

Delete rotations: ≤3

Best for: Frequent updates

AVL Trees

Balance: h ≤ 1.44·lg(n)

Insert rotations: O(log n)

Delete rotations: O(log n)

Best for: Search-heavy workloads

                Conclusion: RB trees sacrifice slightly more height (looser balance) for significantly fewer rotations during updates. This makes them ideal for databases, file systems, and containers where insertions/deletions are frequent.
            

Real-World Applications

Java Standard Library

java.util.TreeMap

java.util.TreeSet

Sorted key-value storage with guaranteed O(log n) operations

C++ STL

std::map, std::set

std::multimap, std::multiset

Associative containers in C++ Standard Template Library

Linux Kernel

CFS Scheduler

Completely Fair Scheduler uses RB trees to manage process scheduling with O(log n) task selection

Database Systems

B+ Tree Indexing

Many databases use RB tree variants for in-memory indexing and maintaining sorted data

Summary & Key Takeaways

RB trees maintain balance through 5 color properties that prevent skew
Height guarantee: h ≤ 2·lg(n+1) ensures O(log n) operations
Insertion: At most 2 rotations, uses 3 cases based on uncle's color
Deletion: At most 3 rotations, uses 4 cases based on sibling configuration
Industry standard: Used in Java, C++, Linux for guaranteed performance

                Master the fundamentals:

                Understand the 5 properties • Practice case identification • Trace insertions and deletions step-by-step • Recognize when to apply rotations vs. recoloring

Complete C++ Node Structure

Complete Node and Tree Class

#include 
using namespace std;

enum Color { BLACK = 0, RED = 1 };

struct Node {
    int key;
    Node* parent;
    Node* left;
    Node* right;
    int color;
    
    Node(int k) : key(k), parent(nullptr), 
                  left(nullptr), right(nullptr), 
                  color(RED) {}
};

class RedBlackTree {
private:
    Node* root;
    Node* TNULL;  // Sentinel NIL
    
    void leftRotate(Node* x);
    void rightRotate(Node* x);
    void insertFix(Node* k);
    void deleteFix(Node* x);
    void rbTransplant(Node* u, Node* v);
    Node* minimum(Node* node);
    void deleteNodeHelper(Node* node, int key);
    
public:
    RedBlackTree();
    void insert(int key);
    void deleteNode(int key);
    Node* search(int key);
};

Reference: Programiz - Complete RB Tree Implementation

Complete C++ Implementation - Constructor & Helpers

Constructor and Helper Methods

RedBlackTree::RedBlackTree() {
    TNULL = new Node(0);
    TNULL->color = BLACK;
    TNULL->left = nullptr;
    TNULL->right = nullptr;
    TNULL->parent = nullptr;
    root = TNULL;
}

Node* RedBlackTree::minimum(Node* node) {
    while (node->left != TNULL)
        node = node->left;
    return node;
}

Node* RedBlackTree::search(int key) {
    Node* curr = root;
    while (curr != TNULL) {
        if (key == curr->key)
            return curr;
        else if (key < curr->key)
            curr = curr->left;
        else
            curr = curr->right;
    }
    return nullptr;  // Not found
}

Note: All operations must use TNULL instead of nullptr for leaf nodes. This simplifies boundary condition handling.

Complete insertFix Implementation

C++ insertFix Method

void RedBlackTree::insertFix(Node* k) {
    Node* u;
    while (k->parent->color == RED) {
        if (k->parent == k->parent->parent->left) {
            u = k->parent->parent->right;  // Uncle
            
            if (u->color == RED) {         // Case 1
                k->parent->color = BLACK;
                u->color = BLACK;
                k->parent->parent->color = RED;
                k = k->parent->parent;
            } else {
                if (k == k->parent->right) { // Case 2
                    k = k->parent;
                    leftRotate(k);
                }
                k->parent->color = BLACK;    // Case 3
                k->parent->parent->color = RED;
                rightRotate(k->parent->parent);
            }
        } else {  // Mirror cases
            u = k->parent->parent->left;
            
            if (u->color == RED) {
                k->parent->color = BLACK;
                u->color = BLACK;
                k->parent->parent->color = RED;
                k = k->parent->parent;
            } else {
                if (k == k->parent->left) {
                    k = k->parent;
                    rightRotate(k);
                }
                k->parent->color = BLACK;
                k->parent->parent->color = RED;
                leftRotate(k->parent->parent);
            }
        }
        if (k == root) break;
    }
    root->color = BLACK;
}

Common Mistakes to Avoid

Forgetting to update parent pointers after rotation - causes dangling pointers
Not handling TNULL properly in conditions - check for TNULL, not nullptr
Incorrect case analysis in fixup - missing some scenarios or wrong conditions
Updating color but forgetting structure changes - rotations must accompany recoloring
Not handling root specially - root has no parent, special case needed

Example: Correct vs Incorrect Rotation

CORRECT

void leftRotate(Node* x) {
  Node* y = x->right;
  x->right = y->left;
  if (y->left != TNULL)
    y->left->parent = x;  // ✓
  y->parent = x->parent;
  // ... rest of code
}

WRONG

void leftRotateWrong(Node* x) {
  Node* y = x->right;
  x->right = y->left;
  // Missing parent update!
  // ✗ BUG: dangling pointer
  y->parent = x->parent;
  // ... rest of code
}

Testing Your Implementation & Resources

Test Cases to Verify Correctness

Insert single node → verify it's root and BLACK
Insert two nodes → verify balance and colors
Insert n nodes in ascending order → verify height is O(log n)
Delete from single node → verify tree is empty
Delete root → verify new root is BLACK
Verify all 5 properties after each operation
Stress test with random insertions/deletions (1000+ operations)

CLRS Textbook

"Introduction to Algorithms" Chapter 13

Authoritative source with complete proofs

Programiz

RB Tree Tutorial

Complete C++ implementation with examples

VisualGo

Interactive Visualization

Step-by-step visual animations of operations

GeeksforGeeks

RB Tree Articles

Multiple articles with code and explanations

                Practice makes perfect!

                Implement RB trees from scratch • Trace each case manually • Use visualizers to verify • Test with edge cases