Algorithm
A Red-Black Tree is a type of self-balancing binary search tree (BST). It maintains balance during insertions and deletions by using a set of rules that ensure the tree remains approximately balanced. Red-Black Trees are commonly used in the implementation of associative containers like sets, maps, and dictionaries.
Here are the key properties of a Red-Black Tree:
- Node Color: Each node in the tree is colored either red or black.
- Root Node: The root is black.
- Leaf Nodes: All leaves (NIL or null nodes) are black. These leaf nodes are considered to be double black, and they don't contain any useful information but serve as placeholders.
- Red-Black Property: Red nodes cannot have red children. In other words, no two consecutive nodes on any path from the root to a leaf can be red.
- Depth Property: For each node, any simple path from this node to any of its descendant leaves contains the same number of black nodes. This property ensures that the tree remains balanced.
These properties guarantee that the longest path from the root to any leaf is no more than twice the length of the shortest path, providing a balance that prevents degeneration into a linked list.
Operations such as insertion, deletion, and search in a Red-Black Tree are designed to maintain these properties, ensuring that the tree remains balanced after each operation. The worst-case time complexity for these operations is O(log n), where n is the number of nodes in the tree.
Red-Black Trees are widely used in many programming languages' standard libraries to implement balanced search trees, and they play a crucial role in maintaining efficient data structures for various applications.
Code Examples
#1 Red-Black Tree implement in Python
Code -
Python Programming
class Node:
def __init__(self, key, color, left=None, right=None, parent=None):
self.key = key
self.color = color
self.left = left
self.right = right
self.parent = parent
class RedBlackTree:
def __init__(self):
self.NIL = Node(None, 'black') # Sentinel node representing NIL (null or leaf) in the tree
self.root = self.NIL
def insert(self, key):
new_node = Node(key, 'red', self.NIL, self.NIL, self.NIL)
self._insert(new_node)
self._insert_fixup(new_node)
def _insert(self, z):
y = self.NIL
x = self.root
while x != self.NIL:
y = x
if z.key < x.key:
x = x.left
else:
x = x.right
z.parent = y
if y == self.NIL:
self.root = z
elif z.key < y.key:
y.left = z
else:
y.right = z
def _insert_fixup(self, z):
while z.parent.color == 'red':
if z.parent == z.parent.parent.left:
y = z.parent.parent.right
if y.color == 'red':
z.parent.color = 'black'
y.color = 'black'
z.parent.parent.color = 'red'
z = z.parent.parent
else:
if z == z.parent.right:
z = z.parent
self._left_rotate(z)
z.parent.color = 'black'
z.parent.parent.color = 'red'
self._right_rotate(z.parent.parent)
else:
y = z.parent.parent.left
if y.color == 'red':
z.parent.color = 'black'
y.color = 'black'
z.parent.parent.color = 'red'
z = z.parent.parent
else:
if z == z.parent.left:
z = z.parent
self._right_rotate(z)
z.parent.color = 'black'
z.parent.parent.color = 'red'
self._left_rotate(z.parent.parent)
self.root.color = 'black'
def _left_rotate(self, x):
y = x.right
x.right = y.left
if y.left != self.NIL:
y.left.parent = x
y.parent = x.parent
if x.parent == self.NIL:
self.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x
x.parent = y
def _right_rotate(self, y):
x = y.left
y.left = x.right
if x.right != self.NIL:
x.right.parent = y
x.parent = y.parent
if y.parent == self.NIL:
self.root = x
elif y == y.parent.left:
y.parent.left = x
else:
y.parent.right = x
x.right = y
y.parent = x
def inorder_traversal(self, node=None):
if node is None:
node = self.root
if node != self.NIL:
self.inorder_traversal(node.left)
print(f"{node.key} ({node.color})", end=" ")
self.inorder_traversal(node.right)
# Example usage
if __name__ == "__main__":
rb_tree = RedBlackTree()
keys = [7, 18, 3, 10, 22, 8, 11, 26]
for key in keys:
rb_tree.insert(key)
print("Inorder Traversal:")
rb_tree.inorder_traversal()
#2 Red-Black Tree implement in Java
Code -
Java Programming
// Red-Black Tree Node
class Node {
int data;
Node parent;
Node left;
Node right;
int color; // 0 for black, 1 for red
public Node(int data) {
this.data = data;
this.color = 1; // New nodes are always red
this.parent = null;
this.left = null;
this.right = null;
}
}
// Red-Black Tree class
public class RedBlackTree {
private Node root;
private Node TNULL;
// Preorder
private void preOrderHelper(Node node) {
if (node != TNULL) {
System.out.print(node.data + " ");
preOrderHelper(node.left);
preOrderHelper(node.right);
}
}
// Inorder
private void inOrderHelper(Node node) {
if (node != TNULL) {
inOrderHelper(node.left);
System.out.print(node.data + " ");
inOrderHelper(node.right);
}
}
// Post order
private void postOrderHelper(Node node) {
if (node != TNULL) {
postOrderHelper(node.left);
postOrderHelper(node.right);
System.out.print(node.data + " ");
}
}
// Search the tree
private 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);
}
// Balance the tree after deletion of a node
private void fixDelete(Node x) {
Node s;
while (x != root && x.color == 0) {
if (x == x.parent.left) {
s = x.parent.right;
if (s.color == 1) {
s.color = 0;
x.parent.color = 1;
leftRotate(x.parent);
s = x.parent.right;
}
if (s.left.color == 0 && s.right.color == 0) {
s.color = 1;
x = x.parent;
} else {
if (s.right.color == 0) {
s.left.color = 0;
s.color = 1;
rightRotate(s);
s = x.parent.right;
}
s.color = x.parent.color;
x.parent.color = 0;
s.right.color = 0;
leftRotate(x.parent);
x = root;
}
} else {
s = x.parent.left;
if (s.color == 1) {
s.color = 0;
x.parent.color = 1;
rightRotate(x.parent);
s = x.parent.left;
}
if (s.right.color == 0 && s.right.color == 0) {
s.color = 1;
x = x.parent;
} else {
if (s.left.color == 0) {
s.right.color = 0;
s.color = 1;
leftRotate(s);
s = x.parent.left;
}
s.color = x.parent.color;
x.parent.color = 0;
s.left.color = 0;
rightRotate(x.parent);
x = root;
}
}
}
x.color = 0;
}
// Transplant the node u with node v
private void transplant(Node u, Node v) {
if (u.parent == null) {
root = v;
} else if (u == u.parent.left) {
u.parent.left = v;
} else {
u.parent.right = v;
}
v.parent = u.parent;
}
// Delete node from the tree
private 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) {
System.out.println("Couldn't find key in the tree");
return;
}
y = z;
int yOriginalColor = y.color;
if (z.left == TNULL) {
x = z.right;
transplant(z, z.right);
} else if (z.right == TNULL) {
x = z.left;
transplant(z, z.left);
} else {
y = minimum(z.right);
yOriginalColor = y.color;
x = y.right;
if (y.parent == z) {
x.parent = y;
} else {
transplant(y, y.right);
y.right = z.right;
y.right.parent = y;
}
transplant(z, y);
y.left = z.left;
y.left.parent = y;
y.color = z.color;
}
if (yOriginalColor == 0) {
fixDelete(x);
}
}
// Balance the tree after insertion of a node
private void fixInsert(Node k){
Node u;
while (k.parent.color == 1) {
if (k.parent == k.parent.parent.right) {
u = k.parent.parent.left; // uncle
if (u.color == 1) {
u.color = 0;
k.parent.color = 0;
k.parent.parent.color = 1;
k = k.parent.parent;
} else {
if (k == k.parent.left) {
k = k.parent;
rightRotate(k);
}
k.parent.color = 0;
k.parent.parent.color = 1;
leftRotate(k.parent.parent);
}
} else {
u = k.parent.parent.right; // uncle
if (u.color == 1) {
u.color = 0;
k.parent.color = 0;
k.parent.parent.color = 1;
k = k.parent.parent; // Move x's grandparent up
} else {
if (k == k.parent.right) {
k = k.parent;
leftRotate(k);
}
k.parent.color = 0;
k.parent.parent.color = 1;
rightRotate(k.parent.parent);
}
}
if (k == root) {
break;
}
}
root.color = 0;
}
// Find the node with the minimum key
private Node minimum(Node node) {
while (node.left != TNULL) {
node = node.left;
}
return node;
}
// Perform left rotation
private void leftRotate(Node x) {
Node y = x.right;
x.right = y.left;
if (y.left != TNULL) {
y.left.parent = x;
}
#3 Red-Black Tree implement in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
// Node structure for Red-Black Tree
typedef struct Node {
int data;
char color; // 'R' for red, 'B' for black
struct Node* parent;
struct Node* left;
struct Node* right;
} Node;
// Tree structure
typedef struct {
Node* root;
Node* nil; // Sentinel node representing NULL
} RedBlackTree;
// Function to create a new node
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}
newNode->data = data;
newNode->color = 'R'; // New nodes are always red
newNode->parent = NULL;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to initialize a Red-Black Tree
RedBlackTree* initializeRedBlackTree() {
RedBlackTree* tree = (RedBlackTree*)malloc(sizeof(RedBlackTree));
if (tree == NULL) {
fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}
tree->nil = createNode(-1);
tree->nil->color = 'B'; // Sentinel node is always black
tree->root = tree->nil; // Initialize root to the sentinel node
return tree;
}
// Function to perform left rotation
void leftRotate(RedBlackTree* tree, Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left != tree->nil) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == tree->nil) {
tree->root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
// Function to perform right rotation
void rightRotate(RedBlackTree* tree, Node* y) {
Node* x = y->left;
y->left = x->right;
if (x->right != tree->nil) {
x->right->parent = y;
}
x->parent = y->parent;
if (y->parent == tree->nil) {
tree->root = x;
} else if (y == y->parent->left) {
y->parent->left = x;
} else {
y->parent->right = x;
}
x->right = y;
y->parent = x;
}
// Function to insert a node into the Red-Black Tree
void insert(RedBlackTree* tree, int data) {
Node* z = createNode(data);
Node* y = tree->nil;
Node* x = tree->root;
while (x != tree->nil) {
y = x;
if (z->data < x->data) {
x = x->left;
} else {
x = x->right;
}
}
z->parent = y;
if (y == tree->nil) {
tree->root = z;
} else if (z->data < y->data) {
y->left = z;
} else {
y->right = z;
}
// Fix the tree after insertion
insertFixup(tree, z);
}
// Function to fix the Red-Black Tree properties after insertion
void insertFixup(RedBlackTree* tree, Node* z) {
while (z->parent->color == 'R') {
if (z->parent == z->parent->parent->left) {
Node* y = z->parent->parent->right;
if (y->color == 'R') {
z->parent->color = 'B';
y->color = 'B';
z->parent->parent->color = 'R';
z = z->parent->parent;
} else {
if (z == z->parent->right) {
z = z->parent;
leftRotate(tree, z);
}
z->parent->color = 'B';
z->parent->parent->color = 'R';
rightRotate(tree, z->parent->parent);
}
} else {
Node* y = z->parent->parent->left;
if (y->color == 'R') {
z->parent->color = 'B';
y->color = 'B';
z->parent->parent->color = 'R';
z = z->parent->parent;
} else {
if (z == z->parent->left) {
z = z->parent;
rightRotate(tree, z);
}
z->parent->color = 'B';
z->parent->parent->color = 'R';
leftRotate(tree, z->parent->parent);
}
}
}
tree->root->color = 'B';
}
// Function to print the Red-Black Tree in-order
void inOrderTraversal(Node* x) {
if (x != NULL) {
inOrderTraversal(x->left);
printf("%d ", x->data);
inOrderTraversal(x->right);
}
}
// Function to print the Red-Black Tree
void printRedBlackTree(RedBlackTree* tree) {
printf("In-Order Traversal: ");
inOrderTraversal(tree->root);
printf("\n");
}
// Function to free the memory allocated for the Red-Black Tree nodes
void freeRedBlackTree(Node* x) {
if (x != NULL) {
freeRedBlackTree(x->left);
freeRedBlackTree(x->right);
free(x);
}
}
// Function to destroy the Red-Black Tree
void destroyRedBlackTree(RedBlackTree* tree) {
freeRedBlackTree(tree->root);
free(tree->nil);
free(tree);
}
int main() {
RedBlackTree* tree = initializeRedBlackTree();
// Insert nodes into the Red-Black Tree
insert(tree, 10);
insert(tree, 20);
insert(tree, 15);
insert(tree, 5);
insert(tree, 25);
// Print the Red-Black Tree
printRedBlackTree(tree);
// Destroy the Red-Black Tree
destroyRedBlackTree(tree);
return 0;
}
#4 Red-Black Tree implement in C++
Code -
C++ Programming
#include <iostream>
enum Color { RED, BLACK };
template < typename T>
struct Node {
T data;
Color color;
Node *parent, *left, *right;
// Constructor
Node(T value) : data(value), color(RED), parent(nullptr), left(nullptr), right(nullptr) {}
};
template < typename T>
class RedBlackTree {
private:
Node* root;
// Helper functions
void leftRotate(Node* x);
void rightRotate(Node < T>* y);
void insertFixup(Node* z);
void transplant(Node < T>* u, Node* v);
void deleteFixup(Node* x);
Node < T>* minimum(Node* subtreeRoot);
public:
// Constructor
RedBlackTree() : root(nullptr) {}
// Public interface
void insert(T value);
void remove(T value);
void printInOrder();
};
// Implementation of the helper functions and public interface...
int main() {
RedBlackTree < int> rbTree;
// Example usage
rbTree.insert(10);
rbTree.insert(5);
rbTree.insert(15);
rbTree.insert(3);
rbTree.insert(7);
rbTree.insert(12);
rbTree.insert(18);
std::cout << "In-order traversal: ";
rbTree.printInOrder();
rbTree.remove(7);
std::cout << "\nAfter removing 7, in-order traversal: ";
rbTree.printInOrder();
return 0;
}
// Implementation of the Red-Black Tree methods...
Demonstration
Red-Black Tree-DevsEnv