Red-Black Tree – Complete Guide to Balancing

With Diagrams, Step-by-Step Rotations, Insertion, Deletion, and Full C Code

Red-Black Tree – Complete Guide to Balancing

With Diagrams, Step-by-Step Rotations, Insertion, Deletion, and Full C Code

Red-Black Tree – Complete Guide to Balancing

With Diagrams, Step-by-Step Rotations, Insertion, Deletion, and Full C Code

1. What is a Red-Black Tree?

Red-Black Tree is a self-balancing Binary Search Tree that maintains approximate balance using color properties.

Key Properties (5 Rules)

#	Property
1	Every node is RED or BLACK
2	Root is always BLACK
3	All leaf (NULL) nodes are BLACK
4	RED node cannot have RED child (No two REDs adjacent)
5	Every path from node to descendant leaf has same number of BLACK nodes (Black Height)

2. Why Red-Black Tree?

Feature	AVL	Red-Black
Balance	Strict	Relaxed
Insert/Delete	More rotations	Fewer rotations
Search	Slightly faster	Slightly slower
Best for	Lookup-heavy	Insert/Delete-heavy (e.g., `std::map` in C++)

O(log n) for all operations
Fewer restructurings → Better for frequent updates

3. Node Structure

#define RED 1
#define BLACK 0

struct RBNode {
    int data;
    int color;  // RED or BLACK
    struct RBNode *left, *right, *parent;
};

4. Helper Functions

struct RBNode* createNode(int data) {
    struct RBNode* node = (struct RBNode*)malloc(sizeof(struct RBNode));
    node->data = data;
    node->color = RED;  // New node is RED
    node->left = node->right = node->parent = NULL;
    return node;
}

int isRed(struct RBNode* node) {
    return node != NULL && node->color == RED;
}

5. Rotations (Same as AVL)

Left Rotate

void leftRotate(struct RBNode** root, struct RBNode* x) {
    struct RBNode* y = x->right;
    x->right = y->left;
    if (y->left != NULL)
        y->left->parent = x;
    y->parent = x->parent;
    if (x->parent == NULL)
        *root = y;
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;
    y->left = x;
    x->parent = y;
}

Right Rotate

void rightRotate(struct RBNode** root, struct RBNode* y) {
    struct RBNode* x = y->left;
    y->left = x->right;
    if (x->right != NULL)
        x->right->parent = y;
    x->parent = y->parent;
    if (y->parent == NULL)
        *root = x;
    else if (y == y->parent->right)
        y->parent->right = x;
    else
        y->parent->left = x;
    x->right = y;
    y->parent = x;
}

6. INSERTION & BALANCING

Step 1: Insert as in BST (New node = RED)

Step 2: Fix Violations

Violation: RED parent + RED child

Cases to Fix

Case	Condition	Fix
Case 1	Parent is BLACK	Do nothing
Case 2	Uncle is RED	Recolor
Case 3	Uncle is BLACK	Rotate + Recolor

Case 2: Uncle is RED (Recolor)

        G (B)
       /   \
     P (R)  U (R)
    /
   N (R)

Fix:
- Make P and U BLACK
- Make G RED
- Recurse on G

Case 3: Uncle is BLACK

Subcase 3A: Left-Left (LL)

        G (B)
       /   
     P (R)  
    /       
   N (R)

Fix:
1. Right rotate on G
2. Swap colors of P and G

     P (B)
    /   \
  N (R)  G (R)

Subcase 3B: Left-Right (LR)

        G (B)
       /   
     P (R)  
      \     
       N (R)

Fix:
1. Left rotate on P
2. Treat as LL case

Subcase 3C: Right-Right (RR)

Symmetric to LL

Subcase 3D: Right-Left (RL)

Symmetric to LR

7. Full Insert Function

void insertFixup(struct RBNode** root, struct RBNode* node) {
    while (node->parent && isRed(node->parent)) {
        struct RBNode* parent = node->parent;
        struct RBNode* grandparent = parent->parent;

        if (parent == grandparent->left) {
            struct RBNode* uncle = grandparent->right;

            // Case 2: Uncle RED
            if (isRed(uncle)) {
                parent->color = BLACK;
                uncle->color = BLACK;
                grandparent->color = RED;
                node = grandparent;
            } else {
                // Case 3B: LR
                if (node == parent->right) {
                    leftRotate(root, parent);
                    node = parent;
                    parent = node->parent;
                }
                // Case 3A: LL
                rightRotate(root, grandparent);
                parent->color = BLACK;
                grandparent->color = RED;
                node = parent;
            }
        } else {
            // Symmetric for right side
            struct RBNode* uncle = grandparent->left;
            if (isRed(uncle)) {
                parent->color = BLACK;
                uncle->color = BLACK;
                grandparent->color = RED;
                node = grandparent;
            } else {
                if (node == parent->left) {
                    rightRotate(root, parent);
                    node = parent;
                    parent = node->parent;
                }
                leftRotate(root, grandparent);
                parent->color = BLACK;
                grandparent->color = RED;
                node = parent;
            }
        }
    }
    (*root)->color = BLACK;  // Root always BLACK
}

void insert(struct RBNode** root, int data) {
    struct RBNode* node = createNode(data);
    struct RBNode* parent = NULL;
    struct RBNode* current = *root;

    // BST Insert
    while (current != NULL) {
        parent = current;
        if (data < current->data)
            current = current->left;
        else
            current = current->right;
    }

    node->parent = parent;
    if (parent == NULL)
        *root = node;
    else if (data < parent->data)
        parent->left = node;
    else
        parent->right = node;

    insertFixup(root, node);
}

8. DELETION & BALANCING

Step 1: Delete as in BST

Step 2: Fix if removed BLACK node

Double Black or Black Deficit

Cases

Case	Fix
Sibling RED	Recolor + Rotate
Sibling BLACK, both nephews BLACK	Recolor sibling RED
Sibling BLACK, one nephew RED	Rotate + Recolor

Full Deletion Code (Simplified)

void deleteFixup(struct RBNode** root, struct RBNode* x) {
    while (x != *root && !isRed(x)) {
        if (x == x->parent->left) {
            struct RBNode* sibling = x->parent->right;
            if (isRed(sibling)) {
                sibling->color = BLACK;
                x->parent->color = RED;
                leftRotate(root, x->parent);
                sibling = x->parent->right;
            }
            if (!isRed(sibling->left) && !isRed(sibling->right)) {
                sibling->color = RED;
                x = x->parent;
            } else {
                if (!isRed(sibling->right)) {
                    sibling->left->color = BLACK;
                    sibling->color = RED;
                    rightRotate(root, sibling);
                    sibling = x->parent->right;
                }
                sibling->color = x->parent->color;
                x->parent->color = BLACK;
                sibling->right->color = BLACK;
                leftRotate(root, x->parent);
                x = *root;
            }
        } else {
            // Symmetric for right
        }
    }
    if (x) x->color = BLACK;
}

9. Example: Insert 10, 20, 30

Insert 10 (RED) → Root = BLACK
     10(B)

Insert 20 (RED)
     10(B)
      \
      20(R)

Insert 30 (RED) → RED-RED violation
     10(B)
      \
      20(R)
       \
       30(R)

Uncle = NULL (BLACK) → RR Case
→ Left Rotate on 10
     20(B)
    /   \
  10(R) 30(R)

Recolor: 20 → BLACK, 10 & 30 → BLACK? No, just fix root
→ Root = 20(B), 10 & 30 = RED

10. Black Height

Path: Root → Leaf
Count BLACK nodes (ignore RED)
All paths must have same count

11. Time Complexity

Operation	Time
Search	O(log n)
Insert	O(log n)
Delete	O(log n)
Rotation	O(1)

12. Comparison Table

Feature	AVL	Red-Black
Balance		BF
Height	~1.44 log n	~2 log n
Rotations	More	Less
Insert/Delete	Slower	Faster
Search	Faster	Slower
Memory	Less	More (color + parent)

13. Visual: Insert Sequence

Insert: 40, 30, 50, 20, 35, 25

After balancing:
        30(B)
       /    \
     20(B)  40(B)
    /     /   \
  25(R) 35(R) 50(R)

14. Full Working C Code (Insert Only)

#include <stdio.h>
#include <stdlib.h>

#define RED 1
#define BLACK 0

struct RBNode {
    int data;
    int color;
    struct RBNode *left, *right, *parent;
};

// ... (createNode, rotations, insertFixup, insert) ...

void inorder(struct RBNode* root) {
    if (root) {
        inorder(root->left);
        printf("%d(%s) ", root->data, root->color == RED ? "R" : "B");
        inorder(root->right);
    }
}

int main() {
    struct RBNode* root = NULL;
    int keys[] = {10, 20, 30, 40, 50, 25};
    for (int i = 0; i < 6; i++)
        insert(&root, keys[i]);

    printf("Inorder: ");
    inorder(root);
    return 0;
}

15. Practice Problems

Draw tree after inserting 1 to 10
Simulate deletion of 20
Count black height
Implement full delete
Compare rotations: AVL vs RB on 1000 inserts

16. Key Takeaways

Insight
Red-Black = BST + Color Rules
Only 3 main cases in insert
Fewer rotations than AVL
Root always BLACK
No two REDs adjacent
Black height constant
Used in C++ STL, Java HashMap, Linux kernel

End of Red-Black Tree Balancing

Last updated: Nov 12, 2025

Red-Black Tree – Complete Guide to Balancing

With Diagrams, Step-by-Step Rotations, Insertion, Deletion, and Full C Code