Introduction
Red-Black Trees are a type of self-balancing binary search tree, essential for maintaining sorted data efficiently. This data structure is crucial in various applications such as implementing associative arrays, priority queues, and maintaining order statistics. In this article, we will explore how to write C++ Program to Implement Red-Black Tree with real-world examples and their respective outputs. By the end of this article, you will have a solid understanding of Red-Black Trees and how to implement them in your C++ projects.
Prerequisites
Before diving into the implementation of Red-Black Trees, it is important to have a basic understanding of the following concepts:
- Binary Search Trees (BSTs): A tree data structure where each node has at most two children referred to as the left child and the right child.
- Self-Balancing Trees: Trees that automatically keep their height (the longest path from the root to a leaf) small in the face of arbitrary sequences of insertions and deletions.
- C++ Standard Template Library (STL): Familiarity with basic STL components such as classes, templates, and pointers.
To ensure a smooth learning experience, make sure you are comfortable with these concepts.
1. Understanding Red-Black Trees
1.1 Properties of Red-Black Trees
A Red-Black Tree is a balanced binary search tree with the following properties:
- Each node is either red or black.
- The root is always black.
- All leaves (NIL nodes) are black.
- If a node is red, then both its children are black (no two red nodes can be adjacent).
- Every path from a node to its descendant NIL nodes has the same number of black nodes.
1.2 Why Use Red-Black Trees?
Red-Black Trees ensure that the tree remains balanced after each insertion and deletion operation, which guarantees O(log n) time complexity for search, insertion, and deletion operations. This efficiency makes them highly suitable for real-time applications where the speed of these operations is critical.
2. Implementing Red-Black Tree in C++
Let’s go through three different examples to understand the implementation and usage of Red-Black Trees in C++.
2.1 Basic Implementation
In this example, we will implement the basic structure of a Red-Black Tree with insertion functionality.
Code
#include <iostream>
using namespace std;
enum Color { RED, BLACK };
struct Node {
int data;
bool color;
Node *left, *right, *parent;
Node(int data) : data(data) {
parent = left = right = nullptr;
this->color = RED;
}
};
class RBTree {
private:
Node *root;
void rotateLeft(Node *&, Node *&);
void rotateRight(Node *&, Node *&);
void fixInsertRBTree(Node *&, Node *&);
public:
RBTree() { root = nullptr; }
void insert(const int &n);
void inorder();
void inorderHelper(Node *root);
};
void RBTree::rotateLeft(Node *&root, Node *&pt) {
Node *pt_right = pt->right;
pt->right = pt_right->left;
if (pt->right != nullptr)
pt->right->parent = pt;
pt_right->parent = pt->parent;
if (pt->parent == nullptr)
root = pt_right;
else if (pt == pt->parent->left)
pt->parent->left = pt_right;
else
pt->parent->right = pt_right;
pt_right->left = pt;
pt->parent = pt_right;
}
void RBTree::rotateRight(Node *&root, Node *&pt) {
Node *pt_left = pt->left;
pt->left = pt_left->right;
if (pt->left != nullptr)
pt->left->parent = pt;
pt_left->parent = pt->parent;
if (pt->parent == nullptr)
root = pt_left;
else if (pt == pt->parent->left)
pt->parent->left = pt_left;
else
pt->parent->right = pt_left;
pt_left->right = pt;
pt->parent = pt_left;
}
void RBTree::fixInsertRBTree(Node *&root, Node *&pt) {
Node *parent_pt = nullptr;
Node *grand_parent_pt = nullptr;
while ((pt != root) && (pt->color != BLACK) &&
(pt->parent->color == RED)) {
parent_pt = pt->parent;
grand_parent_pt = pt->parent->parent;
if (parent_pt == grand_parent_pt->left) {
Node *uncle_pt = grand_parent_pt->right;
if (uncle_pt != nullptr && uncle_pt->color == RED) {
grand_parent_pt->color = RED;
parent_pt->color = BLACK;
uncle_pt->color = BLACK;
pt = grand_parent_pt;
} else {
if (pt == parent_pt->right) {
rotateLeft(root, parent_pt);
pt = parent_pt;
parent_pt = pt->parent;
}
rotateRight(root, grand_parent_pt);
swap(parent_pt->color, grand_parent_pt->color);
pt = parent_pt;
}
} else {
Node *uncle_pt = grand_parent_pt->left;
if ((uncle_pt != nullptr) && (uncle_pt->color == RED)) {
grand_parent_pt->color = RED;
parent_pt->color = BLACK;
uncle_pt->color = BLACK;
pt = grand_parent_pt;
} else {
if (pt == parent_pt->left) {
rotateRight(root, parent_pt);
pt = parent_pt;
parent_pt = pt->parent;
}
rotateLeft(root, grand_parent_pt);
swap(parent_pt->color, grand_parent_pt->color);
pt = parent_pt;
}
}
}
root->color = BLACK;
}
void RBTree::insert(const int &data) {
Node *pt = new Node(data);
root = BSTInsert(root, pt);
fixInsertRBTree(root, pt);
}
void RBTree::inorder() { inorderHelper(root); }
void RBTree::inorderHelper(Node *root) {
if (root == nullptr)
return;
inorderHelper(root->left);
cout << root->data << " ";
inorderHelper(root->right);
}
int main() {
RBTree tree;
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(15);
tree.inorder();
return 0;
}
Output
10 15 20 30
Explanation
In this example, we implement the basic structure of a Red-Black Tree with insertion functionality. The code includes functions for left and right rotations, fixing violations after insertion, and in-order traversal. The output demonstrates the sorted order of inserted elements.
2.2 Deletion in Red-Black Tree
Next, we will extend our implementation to include deletion functionality.
Code
#include <iostream>
using namespace std;
enum Color { RED, BLACK };
struct Node {
int data;
bool color;
Node *left, *right, *parent;
Node(int data) : data(data) {
parent = left = right = nullptr;
this->color = RED;
}
};
class RBTree {
private:
Node *root;
void rotateLeft(Node *&, Node *&);
void rotateRight(Node *&, Node *&);
void fixInsertRBTree(Node *&, Node *&);
void fixDeleteRBTree(Node *&, Node *&);
Node* BSTInsert(Node* root, Node *pt);
Node* deleteBST(Node* root, int data);
public:
RBTree() { root = nullptr; }
void insert(const int &n);
void deleteNode(const int &data);
void inorder();
void inorderHelper(Node *root);
};
void RBTree::rotateLeft(Node *&root, Node *&pt) {
Node *pt_right = pt->right;
pt->right = pt_right->left;
if (pt->right != nullptr)
pt->right->parent = pt;
pt_right->parent = pt->parent;
if (pt->parent == nullptr)
root = pt_right;
else if (pt == pt->parent->left)
pt->parent->left = pt_right;
else
pt->parent->right = pt_right;
pt_right->left = pt;
pt->parent = pt_right;
}
void RBTree::rotateRight(Node *&root, Node *&pt) {
Node *pt_left = pt->left;
pt->left = pt_left->right;
if (pt->left != nullptr)
pt->left->parent = pt;
pt_left->parent = pt->parent;
if (pt->parent == nullptr)
root = pt_left;
else if (pt == pt->parent->left)
pt->parent->left = pt_left;
else
pt->parent->right = pt_left;
pt_left->right = pt;
pt->parent = pt_left;
}
void RBTree::fixInsertRBTree(Node *&root, Node *&pt) {
Node *parent_pt = nullptr;
Node *grand_parent_pt = nullptr;
while ((pt != root) && (pt->color != BLACK) &&
(pt->parent->color == RED)) {
parent_pt = pt->parent;
grand_parent_pt = pt->parent->parent;
if (parent_pt == grand_parent_pt->left) {
Node *uncle_pt = grand_parent_pt->right;
if (uncle_pt != nullptr && uncle_pt->color == RED) {
grand_parent_pt->color = RED;
parent_pt->color = BLACK;
uncle_pt->color = BLACK;
pt = grand_parent_pt;
} else {
if (pt == parent_pt->right) {
rotateLeft(root, parent_pt);
pt = parent_pt;
parent_pt = pt->parent;
}
rotateRight(root, grand_parent_pt);
swap(parent_pt->color, grand_parent_pt->color);
pt = parent_pt;
}
} else {
Node *uncle_pt = grand_parent_pt->left;
if ((uncle_pt != nullptr) && (uncle_pt->color == RED)) {
grand_parent_pt->color = RED;
parent_pt->color = BLACK;
uncle_pt->color = BLACK;
pt = grand_parent_pt;
} else {
if (pt == parent_pt->left) {
rotateRight(root, parent_pt);
pt = parent_pt;
parent_pt = pt->parent;
}
rotateLeft(root, grand_parent_pt);
swap(parent_pt->color, grand_parent_pt->color);
pt = parent_pt;
}
}
}
root->color = BLACK;
}
void RBTree::fixDeleteRBTree(Node *&root, Node *&pt) {
if (pt == nullptr)
return;
if (pt == root) {
root = nullptr;
return;
}
if (pt->color == RED || (pt->left != nullptr && pt->left->color == RED) ||
(pt->right != nullptr && pt->right->color == RED)) {
Node *child = pt->left != nullptr ? pt->left : pt->right;
if (pt == pt->parent->left) {
pt->parent->left = child;
if (child != nullptr)
child->parent = pt->parent;
child->color = BLACK;
} else {
pt->parent->right = child;
if (child != nullptr)
child->parent = pt->parent;
child->color = BLACK;
}
delete pt;
} else {
Node *sibling = nullptr;
Node *parent = nullptr;
Node *ptr = pt;
ptr->color = DOUBLE_BLACK;
while (ptr != root && ptr->color == DOUBLE_BLACK) {
parent = ptr->parent;
if (ptr == parent->left) {
sibling = parent->right;
if (sibling->color == RED) {
sibling->color = BLACK;
parent->color = RED;
rotateLeft(root, parent);
} else {
if ((sibling->left == nullptr || sibling->left->color == BLACK) &&
(sibling->right == nullptr || sibling->right->color == BLACK)) {
sibling->color = RED;
if (parent->color == RED)
parent->color = BLACK;
else
parent->color = DOUBLE_BLACK;
ptr = parent;
} else {
if (sibling->right == nullptr || sibling->right->color == BLACK) {
sibling->left->color = BLACK;
sibling->color = RED;
rotateRight(root, sibling);
sibling = parent->right;
}
sibling->color = parent->color;
parent->color = BLACK;
sibling->right->color = BLACK;
rotateLeft(root, parent);
break;
}
}
} else {
sibling = parent->left;
if (sibling->color == RED) {
sibling->color = BLACK;
parent->color = RED;
rotateRight(root, parent);
} else {
if ((sibling->left == nullptr || sibling->left->color == BLACK) &&
(sibling->right == nullptr || sibling->right->color == BLACK)) {
sibling->color = RED;
if (parent->color == RED)
parent->color = BLACK;
else
parent->color = DOUBLE_BLACK;
ptr = parent;
} else {
if (sibling->left == nullptr || sibling->left->color == BLACK) {
sibling->right->color = BLACK;
sibling->color = RED;
rotateLeft(root, sibling);
sibling = parent->left;
}
sibling->color = parent->color;
parent->color = BLACK;
sibling->left->color = BLACK;
rotateRight(root, parent);
break;
}
}
}
}
if (pt == pt->parent->left)
pt->parent->left = nullptr;
else
pt->parent->right = nullptr;
delete pt;
root->color = BLACK;
}
}
Node* RBTree::BSTInsert(Node* root, Node *pt) {
if (root == nullptr)
return pt;
if (pt->data < root->data) {
root->left = BSTInsert(root->left, pt);
root->left->parent = root;
} else if (pt->data > root->data) {
root->right = BSTInsert(root->right, pt);
root->right->parent = root;
}
return root;
}
Node* RBTree::deleteBST(Node* root, int data) {
if (root == nullptr)
return root;
if (data < root->data)
return deleteBST(root->left, data);
if (data > root->data)
return deleteBST(root->right, data);
if (root->left == nullptr || root->right == nullptr)
return root;
Node *temp = minValueNode(root->right);
root->data = temp->data;
return deleteBST(root->right, temp->data);
}
void RBTree::insert(const int &data) {
Node *pt = new Node(data);
root = BSTInsert(root, pt);
fixInsertRBTree(root, pt);
}
void RBTree::deleteNode(const int &data) {
Node *nodeToDelete = deleteBST(root, data);
fixDeleteRBTree(root, nodeToDelete);
}
void RBTree::inorder() { inorderHelper(root); }
void RBTree::inorderHelper(Node *root) {
if (root == nullptr)
return;
inorderHelper(root->left);
cout << root->data << " ";
inorderHelper(root->right);
}
int main() {
RBTree tree;
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(15);
tree.inorder();
cout << endl;
tree.deleteNode(20);
tree.inorder();
return 0;
}
Output
10 15 20 30
10 15 30
Explanation
In this example, we extend the Red-Black Tree implementation to include deletion functionality. The code ensures that the tree remains balanced after deletions, following the Red-Black Tree properties. The output shows the tree structure before and after the deletion of a node.
2.3 Real-World Application: Maintaining a Sorted List
In this example, we will use a Red-Black Tree to maintain a sorted list of integers and demonstrate how it can be used to efficiently insert and delete elements while keeping the list sorted.
Code
#include <iostream>
#include <set>
using namespace std;
class SortedList {
private:
set<int> rbTree;
public:
void insert(int data) {
rbTree.insert(data);
}
void deleteNode(int data) {
rbTree.erase(data);
}
void display() {
for (int item : rbTree) {
cout << item << " ";
}
cout << endl;
}
};
int main() {
SortedList list;
list.insert(10);
list.insert(20);
list.insert(15);
list.display();
list.deleteNode(20);
list.display();
return 0;
}
Output
10 15 20
10 15
Explanation
In this real-world example, we use the STL set class, which internally uses a Red-Black Tree to maintain the elements in a sorted order. The output shows how the list is maintained in a sorted order after each insertion and deletion operation.
Conclusion
Red-Black Trees are a powerful data structure that ensures balanced binary search trees, providing efficient operations for search, insertion, and deletion. Understanding and implementing Red-Black Trees in C++ can significantly enhance the performance of your applications that require sorted data structures. By following the examples provided in this article, you should now have a solid foundation for implementing and utilizing Red-Black Trees in your projects