C++ • SELF-BALANCING BST
Red-Black Tree (Insertion, Deletion, Display)
C++ Implementation
red_black_tree.cpp
#include <iostream>
using namespace std;
enum Color { RED, BLACK };
struct Node {
int data;
Color color;
Node *left, *right, *parent;
Node(int val) : data(val), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};
class RedBlackTree {
Node* root;
Node* TNULL;
// Initialize NULL leaf node in constructor
void initializeNULLNode(Node* node, Node* parent) {
node->data = 0;
node->color = BLACK;
node->left = nullptr;
node->right = nullptr;
node->parent = parent;
}
void preOrderHelper(Node* node) {
if (node != TNULL) {
cout << node->data << "(" << (node->color == RED ? "R" : "B") << ") ";
preOrderHelper(node->left);
preOrderHelper(node->right);
}
}
void inOrderHelper(Node* node) {
if (node != TNULL) {
inOrderHelper(node->left);
cout << node->data << "(" << (node->color == RED ? "R" : "B") << ") ";
inOrderHelper(node->right);
}
}
void postOrderHelper(Node* node) {
if (node != TNULL) {
postOrderHelper(node->left);
postOrderHelper(node->right);
cout << node->data << "(" << (node->color == RED ? "R" : "B") << ") ";
}
}
Node* searchTreeHelper(Node* node, int key) {
if (node == TNULL || key == node->data) {
return node;
}
if (key < node->data) {
return searchTreeHelper(node->left, key);
}
return searchTreeHelper(node->right, key);
}
void fixDelete(Node* x) {
Node* s;
while (x != root && x->color == BLACK) {
if (x == x->parent->left) {
s = x->parent->right;
if (s->color == RED) {
s->color = BLACK;
x->parent->color = RED;
leftRotate(x->parent);
s = x->parent->right;
}
if (s->left->color == BLACK && s->right->color == BLACK) {
s->color = RED;
x = x->parent;
} else {
if (s->right->color == BLACK) {
s->left->color = BLACK;
s->color = RED;
rightRotate(s);
s = x->parent->right;
}
s->color = x->parent->color;
x->parent->color = BLACK;
s->right->color = BLACK;
leftRotate(x->parent);
x = root;
}
} else {
s = x->parent->left;
if (s->color == RED) {
s->color = BLACK;
x->parent->color = RED;
rightRotate(x->parent);
s = x->parent->left;
}
if (s->right->color == BLACK && s->left->color == BLACK) {
s->color = RED;
x = x->parent;
} else {
if (s->left->color == BLACK) {
s->right->color = BLACK;
s->color = RED;
leftRotate(s);
s = x->parent->left;
}
s->color = x->parent->color;
x->parent->color = BLACK;
s->left->color = BLACK;
rightRotate(x->parent);
x = root;
}
}
}
x->color = BLACK;
}
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;
}
void deleteNodeHelper(Node* node, int key) {
Node* z = TNULL;
Node* x, *y;
while (node != TNULL) {
if (node->data == key) {
z = node;
}
if (node->data <= key) {
node = node->right;
} else {
node = node->left;
}
}
if (z == TNULL) {
cout << "Key not found in the tree" << endl;
return;
}
y = z;
Color y_original_color = y->color;
if (z->left == TNULL) {
x = z->right;
rbTransplant(z, z->right);
} else if (z->right == TNULL) {
x = z->left;
rbTransplant(z, z->left);
} else {
y = minimum(z->right);
y_original_color = y->color;
x = y->right;
if (y->parent == z) {
x->parent = y;
} else {
rbTransplant(y, y->right);
y->right = z->right;
y->right->parent = y;
}
rbTransplant(z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}
delete z;
if (y_original_color == BLACK) {
fixDelete(x);
}
}
void fixInsert(Node* k) {
Node* u;
while (k->parent->color == RED) {
if (k->parent == k->parent->parent->left) {
u = k->parent->parent->right;
if (u->color == RED) {
u->color = BLACK;
k->parent->color = BLACK;
k->parent->parent->color = RED;
k = k->parent->parent;
} else {
if (k == k->parent->right) {
k = k->parent;
leftRotate(k);
}
k->parent->color = BLACK;
k->parent->parent->color = RED;
rightRotate(k->parent->parent);
}
} else {
u = k->parent->parent->left;
if (u->color == RED) {
u->color = BLACK;
k->parent->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;
}
public:
// Constructor
RedBlackTree() {
TNULL = new Node(0);
TNULL->color = BLACK;
TNULL->left = nullptr;
TNULL->right = nullptr;
root = TNULL;
}
void preorder() {
preOrderHelper(this->root);
}
void inorder() {
inOrderHelper(this->root);
}
void postorder() {
postOrderHelper(this->root);
}
Node* searchTree(int k) {
return searchTreeHelper(this->root, k);
}
Node* minimum(Node* node) {
while (node->left != TNULL) {
node = node->left;
}
return node;
}
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) {
this->root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
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) {
this->root = y;
} else if (x == x->parent->right) {
x->parent->right = y;
} else {
x->parent->left = y;
}
y->right = x;
x->parent = y;
}
// Insert function
void insert(int key) {
Node* node = new Node(key);
node->parent = nullptr;
node->data = key;
node->left = TNULL;
node->right = TNULL;
node->color = RED;
Node* y = nullptr;
Node* x = this->root;
while (x != TNULL) {
y = x;
if (node->data < x->data) {
x = x->left;
} else {
x = x->right;
}
}
node->parent = y;
if (y == nullptr) {
root = node;
} else if (node->data < y->data) {
y->left = node;
} else {
y->right = node;
}
if (node->parent == nullptr) {
node->color = BLACK;
return;
}
if (node->parent->parent == nullptr) {
return;
}
fixInsert(node);
}
// Delete function
void deleteNode(int data) {
deleteNodeHelper(this->root, data);
}
};
int main() {
RedBlackTree bst;
bst.insert(55);
bst.insert(40);
bst.insert(65);
bst.insert(60);
bst.insert(75);
bst.insert(57);
cout << "InOrder Traversal: ";
bst.inorder();
cout << endl;
bst.deleteNode(40);
cout << "InOrder Traversal after deleting 40: ";
bst.inorder();
cout << endl;
return 0;
}Sample Actions
Insert: 55, 40, 65, 60, 75, 57 Delete: 40
Output
InOrder Traversal: 40(B) 55(B) 57(B) 60(R) 65(B) 75(B) InOrder Traversal after deleting 40: 55(B) 57(B) 60(R) 65(B) 75(B)
Line-by-Line Explanation
Code
Meaning
enum Color { RED, BLACK };
Defines node colors required by Red-Black Tree balancing rules.
struct Node
Represents a single node in the tree with data, color, left, right, and parent pointers.
class RedBlackTree
Encapsulates the tree structure, sentinel TNULL nodes, and self-balancing methods.
RedBlackTree()
Constructor initializing the root and sentinel null leaf nodes with BLACK color.
leftRotate(Node* x) / rightRotate(...)
Rotates sub-trees around node x to maintain balance properties during insert/delete.
void insert(int key)
Standard BST insertion followed by calling fixInsert() to resolve red-black violations.
void fixInsert(Node* k)
Recolors and rotates nodes if double-RED violations occur up the parent chain.
void deleteNode(int data)
Removes a node from the tree and triggers fixDelete() if a black node was removed.
void fixDelete(Node* x)
Restores black-height balance after a node deletion.
void inorder()
Displays elements in sorted order along with their node colors (R or B).
return 0;
Signals successful program execution.
How a Red-Black Tree works:
A Red-Black Tree is a self-balancing binary search tree where every node is colored either red or black. By enforcing rules—such as no two red nodes can be adjacent, and every path from root to leaf must have the same number of black nodes—it guarantees that operations like search, insertion, and deletion run in O(log n) time.