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:
- Right rotate on G
- Swap colors of P and G
P (B)
/ \
N (R) G (R)
Subcase 3B: Left-Right (LR)
G (B)
/
P (R)
\
N (R)
Fix:
- Left rotate on P
- 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