Implementing a Red-Black Tree in C++ requires a good understanding of data structures, algorithms, and the specific properties that make Red-Black Trees efficient for various operations. In this tutorial, we will cover everything from the fundamental concepts to the complete implementation of a Red-Black Tree in C++.
Introduction to Red-Black Trees
A Red-Black Tree is a type of self-balancing binary search tree. Each node in the tree contains an extra bit for storing the color of the node, which can be either red or black. This color bit is used to ensure the tree remains approximately balanced during insertions and deletions. The balancing of the tree ensures that the operations such as insert, delete, and find can be performed in O(log n) time.
Properties of Red-Black Trees
A Red-Black Tree must satisfy the following properties:
- Root Property: The root is black.
- Red Property: Red nodes cannot have red children (no two consecutive red nodes on any path).
- Black Property: Every path from a node to its descendant null nodes has the same number of black nodes.
- Depth Property: The depth of any path from the root to a leaf is no more than twice the depth of any other path.
These properties ensure that the tree remains balanced, and thus operations remain efficient.
Red-Black Tree Operations
The primary operations we need to implement for a Red-Black Tree are:
- Insertion: Adding a new node to the tree.
- Deletion: Removing an existing node from the tree.
- Search: Finding a node with a given value.
Before diving into the code, let’s discuss how these operations are handled in a Red-Black Tree.
Insertion
Inserting a node in a Red-Black Tree involves the following steps:
- Perform a standard BST insert.
- Color the new node red.
- Fix the tree to maintain the Red-Black properties by performing necessary rotations and recoloring.
Deletion
Deleting a node from a Red-Black Tree involves:
- Perform a standard BST delete.
- Fix the tree to maintain the Red-Black properties by performing necessary rotations and recoloring.
Search
Searching in a Red-Black Tree is similar to searching in a Binary Search Tree. It involves comparing the target value with the current node’s value and recursively searching in the left or right subtree.
Implementation in C++
Let’s start with the implementation. We will define the structure for the nodes first, followed by the Red-Black Tree class that will include methods for insertion, deletion, and search.
Node Structure
#include <iostream>
#include <memory>
enum Color { RED, BLACK };
struct Node {
int data;
bool color;
std::shared_ptr<Node> left, right, parent;
Node(int data) : data(data) {
parent = left = right = nullptr;
color = RED;
}
};Code language: C++ (cpp)Here, we use enum Color to define the color of the nodes. Each node has a data value, color, and pointers to its left child, right child, and parent. The std::shared_ptr is used for automatic memory management.
Red-Black Tree Class
Now let’s define the Red-Black Tree class.
class RedBlackTree {
private:
std::shared_ptr<Node> root;
void rotateLeft(std::shared_ptr<Node>&);
void rotateRight(std::shared_ptr<Node>&);
void fixInsert(std::shared_ptr<Node>&);
void fixDelete(std::shared_ptr<Node>&);
void transplant(std::shared_ptr<Node>&, std::shared_ptr<Node>&);
std::shared_ptr<Node> minimum(std::shared_ptr<Node> node);
void deleteNode(std::shared_ptr<Node>&, int);
void deleteFix(std::shared_ptr<Node>&, std::shared_ptr<Node>&);
public:
RedBlackTree() { root = nullptr; }
void insert(const int& n);
void deleteNode(const int& data);
std::shared_ptr<Node> search(const int& n);
void inorder();
void inorderHelper(std::shared_ptr<Node> node);
};Code language: C++ (cpp)Rotations
Rotations are a key part of maintaining the Red-Black Tree properties. Let’s implement the left and right rotations.
void RedBlackTree::rotateLeft(std::shared_ptr<Node>& x) {
std::shared_ptr<Node> y = x->right;
x->right = y->left;
if (y->left != nullptr) {
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;
}
void RedBlackTree::rotateRight(std::shared_ptr<Node>& x) {
std::shared_ptr<Node> y = x->left;
x->left = y->right;
if (y->right != nullptr) {
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;
}Code language: C++ (cpp)Insertion
The insert method involves inserting a new node like a standard BST and then fixing the tree to maintain the Red-Black properties.
void RedBlackTree::insert(const int& data) {
std::shared_ptr<Node> node = std::make_shared<Node>(data);
std::shared_ptr<Node> y = nullptr;
std::shared_ptr<Node> x = root;
while (x != nullptr) {
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;
}
node->color = RED;
fixInsert(node);
}
void RedBlackTree::fixInsert(std::shared_ptr<Node>& k) {
std::shared_ptr<Node> u;
while (k->parent && k->parent->color == RED) {
if (k->parent == k->parent->parent->right) {
u = k->parent->parent->left;
if (u && 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;
rotateRight(k);
}
k->parent->color = BLACK;
k->parent->parent->color = RED;
rotateLeft(k->parent->parent);
}
} else {
u = k->parent->parent->right;
if (u && 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;
rotateLeft(k);
}
k->parent->color = BLACK;
k->parent->parent->color = RED;
rotateRight(k->parent->parent);
}
}
if (k == root) {
break;
}
}
root->color = BLACK;
}Code language: C++ (cpp)Deletion
Deletion involves removing the node like a standard BST and then fixing the tree to maintain the Red-Black properties.
void RedBlackTree::transplant(std::shared_ptr<Node>& u, std::shared_ptr<Node>& v) {
if (u->parent == nullptr) {
root = v;
} else if (u == u->parent->left) {
u->parent->left = v;
} else {
u->parent->right = v;
}
if (v != nullptr) {
v->parent = u->parent;
}
}
std::shared_ptr<Node> RedBlackTree::minimum(std::shared_ptr<Node> node) {
while (node->left != nullptr) {
node = node->left;
}
return node;
}
void RedBlackTree::deleteNode(const int& data) {
deleteNode(root, data);
}
void RedBlackTree::deleteNode(std::shared_ptr<Node>& node, int key) {
std::shared_ptr<Node> z = nullptr;
std::shared_ptr<Node> x, y;
while (node != nullptr) {
if (node->data == key) {
z = node;
}
if (node->data <= key) {
node = node->right;
} else {
node = node->left;
}
}
if (z == nullptr) {
std::cout << "Key not found in the tree" << std::endl;
return;
}
y = z;
bool yOriginalColor = y->color;
if (z
->left == nullptr) {
x = z->right;
transplant(z, z->right);
} else if (z->right == nullptr) {
x = z->left;
transplant(z, z->left);
} else {
y = minimum(z->right);
yOriginalColor = y->color;
x = y->right;
if (y->parent == z) {
if (x != nullptr) {
x->parent = y;
}
} else {
transplant(y, y->right);
y->right = z->right;
if (y->right != nullptr) {
y->right->parent = y;
}
}
transplant(z, y);
y->left = z->left;
if (y->left != nullptr) {
y->left->parent = y;
}
y->color = z->color;
}
if (yOriginalColor == BLACK) {
deleteFix(x);
}
}
void RedBlackTree::deleteFix(std::shared_ptr<Node>& x) {
std::shared_ptr<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;
rotateLeft(x->parent);
s = x->parent->right;
}
if ((s->left == nullptr || s->left->color == BLACK) && (s->right == nullptr || s->right->color == BLACK)) {
s->color = RED;
x = x->parent;
} else {
if (s->right == nullptr || s->right->color == BLACK) {
if (s->left != nullptr) {
s->left->color = BLACK;
}
s->color = RED;
rotateRight(s);
s = x->parent->right;
}
s->color = x->parent->color;
x->parent->color = BLACK;
if (s->right != nullptr) {
s->right->color = BLACK;
}
rotateLeft(x->parent);
x = root;
}
} else {
s = x->parent->left;
if (s->color == RED) {
s->color = BLACK;
x->parent->color = RED;
rotateRight(x->parent);
s = x->parent->left;
}
if ((s->left == nullptr || s->left->color == BLACK) && (s->right == nullptr || s->right->color == BLACK)) {
s->color = RED;
x = x->parent;
} else {
if (s->left == nullptr || s->left->color == BLACK) {
if (s->right != nullptr) {
s->right->color = BLACK;
}
s->color = RED;
rotateLeft(s);
s = x->parent->left;
}
s->color = x->parent->color;
x->parent->color = BLACK;
if (s->left != nullptr) {
s->left->color = BLACK;
}
rotateRight(x->parent);
x = root;
}
}
}
x->color = BLACK;
}Code language: C++ (cpp)Search
The search operation is straightforward in a Red-Black Tree.
std::shared_ptr<Node> RedBlackTree::search(const int& n) {
std::shared_ptr<Node> temp = root;
while (temp != nullptr) {
if (n < temp->data) {
temp = temp->left;
} else if (n > temp->data) {
temp = temp->right;
} else {
return temp;
}
}
return nullptr;
}Code language: C++ (cpp)Inorder Traversal
Inorder traversal is useful for verifying the structure of the tree.
void RedBlackTree::inorder() {
inorderHelper(root);
}
void RedBlackTree::inorderHelper(std::shared_ptr<Node> node) {
if (node == nullptr) {
return;
}
inorderHelper(node->left);
std::cout << node->data << " ";
inorderHelper(node->right);
}Code language: C++ (cpp)Complete Example
Here is a complete example of a Red-Black Tree in C++ that includes insertion, deletion, and search operations.
#include <iostream>
#include <memory>
enum Color { RED, BLACK };
struct Node {
int data;
bool color;
std::shared_ptr<Node> left, right, parent;
Node(int data) : data(data) {
parent = left = right = nullptr;
color = RED;
}
};
class RedBlackTree {
private:
std::shared_ptr<Node> root;
void rotateLeft(std::shared_ptr<Node>&);
void rotateRight(std::shared_ptr<Node>&);
void fixInsert(std::shared_ptr<Node>&);
void fixDelete(std::shared_ptr<Node>&);
void transplant(std::shared_ptr<Node>&, std::shared_ptr<Node>&);
std::shared_ptr<Node> minimum(std::shared_ptr<Node> node);
void deleteNode(std::shared_ptr<Node>&, int);
void deleteFix(std::shared_ptr<Node>&, std::shared_ptr<Node>&);
public:
RedBlackTree() { root = nullptr; }
void insert(const int& n);
void deleteNode(const int& data);
std::shared_ptr<Node> search(const int& n);
void inorder();
void inorderHelper(std::shared_ptr<Node> node);
};
void RedBlackTree::rotateLeft(std::shared_ptr<Node>& x) {
std::shared_ptr<Node> y = x->right;
x->right = y->left;
if (y->left != nullptr) {
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;
}
void RedBlackTree::rotateRight(std::shared_ptr<Node>& x) {
std::shared_ptr<Node> y = x->left;
x->left = y->right;
if (y->right != nullptr) {
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;
}
void RedBlackTree::insert(const int& data) {
std::shared_ptr<Node> node = std::make_shared<Node>(data);
std::shared_ptr<Node> y = nullptr;
std::shared_ptr<Node> x = root;
while (x != nullptr) {
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;
}
node->color = RED;
fixInsert(node);
}
void RedBlackTree::fixInsert(std::shared_ptr<Node>& k) {
std::shared_ptr<Node> u;
while (k->parent && k->parent->color == RED) {
if (k->parent == k->parent->parent->right) {
u = k->parent->parent->left;
if (u && 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;
rotateRight(k);
}
k->parent->color = BLACK;
k->parent->parent->color = RED;
rotateLeft(k->parent->parent);
}
} else {
u = k->parent->parent->right;
if (u && 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;
rotateLeft(k);
}
k->parent->color = BLACK;
k->parent->parent->color = RED;
rotateRight(k->parent->parent);
}
}
if (k == root) {
break;
}
}
root->color = BLACK;
}
void RedBlackTree::transplant(std::shared_ptr<Node>& u, std::shared_ptr<Node>& v) {
if (u->parent == nullptr) {
root = v;
} else if (u == u->parent->left) {
u->parent->left = v;
} else {
u->parent->right = v
;
}
if (v != nullptr) {
v->parent = u->parent;
}
}
std::shared_ptr<Node> RedBlackTree::minimum(std::shared_ptr<Node> node) {
while (node->left != nullptr) {
node = node->left;
}
return node;
}
void RedBlackTree::deleteNode(const int& data) {
deleteNode(root, data);
}
void RedBlackTree::deleteNode(std::shared_ptr<Node>& node, int key) {
std::shared_ptr<Node> z = nullptr;
std::shared_ptr<Node> x, y;
while (node != nullptr) {
if (node->data == key) {
z = node;
}
if (node->data <= key) {
node = node->right;
} else {
node = node->left;
}
}
if (z == nullptr) {
std::cout << "Key not found in the tree" << std::endl;
return;
}
y = z;
bool yOriginalColor = y->color;
if (z->left == nullptr) {
x = z->right;
transplant(z, z->right);
} else if (z->right == nullptr) {
x = z->left;
transplant(z, z->left);
} else {
y = minimum(z->right);
yOriginalColor = y->color;
x = y->right;
if (y->parent == z) {
if (x != nullptr) {
x->parent = y;
}
} else {
transplant(y, y->right);
y->right = z->right;
if (y->right != nullptr) {
y->right->parent = y;
}
}
transplant(z, y);
y->left = z->left;
if (y->left != nullptr) {
y->left->parent = y;
}
y->color = z->color;
}
if (yOriginalColor == BLACK) {
deleteFix(x);
}
}
void RedBlackTree::deleteFix(std::shared_ptr<Node>& x) {
std::shared_ptr<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;
rotateLeft(x->parent);
s = x->parent->right;
}
if ((s->left == nullptr || s->left->color == BLACK) && (s->right == nullptr || s->right->color == BLACK)) {
s->color = RED;
x = x->parent;
} else {
if (s->right == nullptr || s->right->color == BLACK) {
if (s->left != nullptr) {
s->left->color = BLACK;
}
s->color = RED;
rotateRight(s);
s = x->parent->right;
}
s->color = x->parent->color;
x->parent->color = BLACK;
if (s->right != nullptr) {
s->right->color = BLACK;
}
rotateLeft(x->parent);
x = root;
}
} else {
s = x->parent->left;
if (s->color == RED) {
s->color = BLACK;
x->parent->color = RED;
rotateRight(x->parent);
s = x->parent->left;
}
if ((s->left == nullptr || s->left->color == BLACK) && (s->right == nullptr || s->right->color == BLACK)) {
s->color = RED;
x = x->parent;
} else {
if (s->left == nullptr || s->left->color == BLACK) {
if (s->right != nullptr) {
s->right->color = BLACK;
}
s->color = RED;
rotateLeft(s);
s = x->parent->left;
}
s->color = x->parent->color;
x->parent->color = BLACK;
if (s->left != nullptr) {
s->left->color = BLACK;
}
rotateRight(x->parent);
x = root;
}
}
}
x->color = BLACK;
}
std::shared_ptr<Node> RedBlackTree::search(const int& n) {
std::shared_ptr<Node> temp = root;
while (temp != nullptr) {
if (n < temp->data) {
temp = temp->left;
} else if (n > temp->data) {
temp = temp->right;
} else {
return temp;
}
}
return nullptr;
}
void RedBlackTree::inorder() {
inorderHelper(root);
}
void RedBlackTree::inorderHelper(std::shared_ptr<Node> node) {
if (node == nullptr) {
return;
}
inorderHelper(node->left);
std::cout << node->data << " ";
inorderHelper(node->right);
}
int main() {
RedBlackTree tree;
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(15);
tree.insert(25);
std::cout << "Inorder Traversal of Created Tree\n";
tree.inorder();
std::cout << std::endl;
tree.deleteNode(20);
std::cout << "Inorder Traversal after Deletion of 20\n";
tree.inorder();
std::cout << std::endl;
return 0;
}Code language: C++ (cpp)Conclusion
In this tutorial, we have covered the fundamental concepts of Red-Black Trees and provided a comprehensive implementation in C++. By understanding the properties and operations of Red-Black Trees, you can effectively utilize this data structure to ensure efficient data management and retrieval in your applications.