Red-Black Trees are one of the most widely used data structures in computer science. These trees are a type of self-balancing binary search tree, which means the tree structure is able to maintain a balance between the left and right subtrees. This ensures that operations on the tree, such as insertion, search, and deletion, are performed quickly. Red-Black Trees are used in many applications, from databases to operating systems, and have become an essential tool for any programmer. In this article, we will discuss the fundamentals of Red-Black Trees in C++, including the tree structure, time complexity for operations, and space complexity.
Tree Structure of Red-Black Trees
A Red-Black Tree is a type of binary search tree that is self-balancing. This means that the tree is able to maintain a balance between the left and right subtrees, which ensures that operations on the tree are performed quickly. The tree structure of a Red-Black Tree is composed of nodes, which are connected by edges. Each node is labeled with either a red or black color, and the root node is always black.
Each node in a Red-Black Tree contains three pieces of information: a key, a color, and two pointers to left and right subtrees. The key is used to compare nodes and determine the order of the tree. The color of the node is either red or black, and is used to maintain a balance in the tree. The pointers are used to connect nodes to the left and right subtrees.
The following is a sample implementation of a Red-Black Tree in C++:
struct Node {
int data;
bool color;
Node *left, *right;
};
// Root node is always black
Node *root = new Node(data);
root->color = BLACK;
// Create new node
Node *newNode(int data) {
Node *node = new Node(data);
node->left = node->right = NULL;
node->color = RED;
return node;
}
Time Complexity of Red-Black Trees
The time complexity of Red-Black Trees is dependent on the type of operation being performed. Generally, the time complexity of operations on a Red-Black Tree is O(log n), where n is the number of nodes in the tree. This means that the time complexity of operations on a Red-Black Tree is much smaller than that of a regular binary search tree.
The average time complexity of operations on a Red-Black Tree is O(log n). This means that the time complexity of operations is small and consistent, regardless of the size of the tree.
The worst-case time complexity of operations on a Red-Black Tree is also O(log n). This means that the time complexity of an operation is not affected by the size of the tree, and will always be the same.
Space Complexity of Red-Black Trees
The space complexity of Red-Black Trees is O(n), where n is the number of nodes in the tree. This means that the space complexity is dependent on the size of the tree and increases as the tree grows.
Insertion and Deletion in Red-Black Trees
Insertion and deletion in Red-Black Trees is similar to that of a regular binary search tree, but with the added complexity of maintaining the balance of the tree.
When inserting a new node into the tree, the node must be inserted in the correct position and the color of the node must be set to red. If the node’s parent is red, then the tree must be rebalanced in order to maintain the balance of the tree. The process of rebalancing the tree is complex and beyond the scope of this article.
When deleting a node from the tree, the process is similar to that of insertion. The deleted node must be replaced with another node, and the color of the new node must be set to red. If the new node’s parent is red, then the tree must be rebalanced in order to maintain the balance of the tree.
Conclusion
Red-Black Trees are a type of self-balancing binary search tree, which means the tree structure is able to maintain a balance between the left and right subtrees. This ensures that operations on the tree, such as insertion, search, and deletion, are performed quickly. The time complexity of operations on a Red-Black Tree is O(log n), and the space complexity is O(n). Insertion and deletion in Red-Black Trees is similar to that of a regular binary search tree, but with the added complexity of maintaining the balance of the tree.
Exercises
Write a function to insert a node into a Red-Black Tree.
void insertNode(Node *root, int data) {
Node *newNode = new Node(data);
if (root == NULL) {
root = newNode;
root->color = BLACK;
}
else {
Node *current = root;
while (current != NULL) {
if (data < current->data) {
if (current->left == NULL) {
current->left = newNode;
newNode->color = RED;
break;
}
else {
current = current->left;
}
}
else {
if (current->right == NULL) {
current->right = newNode;
newNode->color = RED;
break;
}
else {
current = current->right;
}
}
}
}
}
Write a function to search for a node in a Red-Black Tree.
Node* searchNode(Node *root, int data) {
if (root == NULL) {
return NULL;
}
else {
Node *current = root;
while (current != NULL) {
if (data == current->data) {
return current;
}
else if (data < current->data) {
current = current->left;
}
else {
current = current->right;
}
}
return NULL;
}
}
Write a function to delete a node from a Red-Black Tree.
void deleteNode(Node* root, int data) {
if (root == NULL) {
return;
}
else {
Node *current = root;
Node *parent = NULL;
while (current != NULL) {
if (data == current->data) {
// Node to be deleted is a leaf node
if (current->left == NULL && current->right == NULL) {
// If node is a left child of its parent
if (parent->left == current)
parent->left = NULL;
// If node is a right child of its parent
else
parent->right = NULL;
delete current;
return;
}
// Node to be deleted has one child
else if (current->left == NULL || current->right == NULL) {
if (current->left == NULL) {
// If node is a left child of its parent
if (parent->left == current)
parent->left = current->right;
// If node is a right child of its parent
else
parent->right = current->right;
}
else {
// If node is a left child of its parent
if (parent->left == current)
parent->left = current->left;
// If node is a right child of its parent
else
parent->right = current->left;
}
delete current;
return;
}
// Node to be deleted has two children
else {
Node *successor = findSuccessor(current);
int successorData = successor->data;
deleteNode(root, successorData);
current->data = successorData;
return;
}
}
else if (data < current->data) {
parent = current;
current = current->left;
}
else {
parent = current;
current = current->right;
}
}
cout << "Element not found." << endl;
}
}
Write a function to find the successor of a node in a Red-Black Tree.
Node* findSuccessor(Node *node) {
if (node->right != NULL) {
Node *current = node->right;
while (current->left != NULL) {
current = current->left;
}
return current;
}
else {
Node *current = node->parent;
while (current != NULL && node == current->right) {
node = current;
current = current->parent;
}
return current;
}
}
Write a function to rebalance a Red-Black Tree.
void rebalanceTree(Node* root) {
// Left-Left case
if (root->left->left != NULL && root->left->color == RED) {
root->color = RED;
root->left->color = BLACK;
rightRotate(root);
}
// Right-Right case
if (root->right->right != NULL && root->right->color == RED) {
root->color = RED;
root->right->color = BLACK;
leftRotate(root);
}
// Left-Right case
if (root->left->right != NULL && root->left->color == RED) {
root->left->right->color = BLACK;
leftRotate(root->left);
rightRotate(root);
}
// Right-Left case
if (root->right->left != NULL && root->right->color == RED) {
root->right->left->color = BLACK;
rightRotate(root->right);
leftRotate(root);
}
}