Algorithm
Insertion in a Red-Black Tree involves adding a new node to the tree while maintaining the properties of a Red-Black Tree. Red-Black Trees are a type of self-balancing binary search tree with additional properties that ensure logarithmic height and efficient operations.
The following are the steps to perform an insertion in a Red-Black Tree:
-
Standard Binary Search Tree Insertion:
- Start by inserting the new node into the Red-Black Tree using standard binary search tree insertion rules. This means finding the appropriate position for the new node based on its key and inserting it as a red node.
-
Color the New Node Red:
- After insertion, color the newly inserted node as red. This step doesn't violate any Red-Black Tree properties.
-
Fix Violations:
- Check and fix any Red-Black Tree properties that might have been violated during the insertion. There are three cases to consider:
a. Case 1: The parent of the newly inserted node is black.
- In this case, no properties are violated, and the tree remains a valid Red-Black Tree.
b. Case 2: The parent of the newly inserted node is red.
- If the parent is red, there is a violation of the property that prohibits consecutive red nodes. To fix this, apply rotations and recoloring as needed.
c. Case 3: The uncle of the newly inserted node is red.
- If both the parent and uncle are red, recolor the parent and uncle to black and the grandparent to red. Then, check if the grandparent violates any properties and recursively fix any issues.
-
Root Color:
- Ensure that the root of the tree is always black. If it's not, change its color to black.
-
Complexity:
- The worst-case time complexity for insertion in a Red-Black Tree is O(log n), where n is the number of nodes in the tree.
Code Examples
#1 Insertion in a 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') # NIL represents a null node in a Red-Black Tree
self.root = self.NIL
def insert(self, key):
new_node = Node(key, 'red')
self._insert(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
z.left = self.NIL
z.right = self.NIL
z.color = 'red'
self._insert_fixup(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
# Example usage:
rb_tree = RedBlackTree()
keys = [10, 20, 30, 15, 25, 5]
for key in keys:
rb_tree.insert(key)
#2 Insertion in a Red-Black Tree implement in Java
Code -
Java Programming
enum Color {
RED,
BLACK
}
class Node {
int key;
Node left, right, parent;
Color color;
public Node(int key) {
this.key = key;
this.color = Color.RED; // New nodes are always red initially
}
}
public class RedBlackTree {
private Node root;
private Node nil; // Represents null in the original algorithm
public RedBlackTree() {
nil = new Node(-1);
nil.color = Color.BLACK;
root = nil;
}
// Other Red-Black Tree methods...
public void insert(int key) {
Node newNode = new Node(key);
insertNode(newNode);
fixInsert(newNode);
}
private void insertNode(Node newNode) {
Node parent = nil;
Node current = root;
while (current != nil) {
parent = current;
if (newNode.key < current.key) {
current = current.left;
} else {
current = current.right;
}
}
newNode.parent = parent;
if (parent == nil) {
root = newNode; // Tree was empty
} else if (newNode.key < parent.key) {
parent.left = newNode;
} else {
parent.right = newNode;
}
newNode.left = nil;
newNode.right = nil;
newNode.color = Color.RED; // New nodes are always red initially
}
private void fixInsert(Node newNode) {
while (newNode.parent.color == Color.RED) {
if (newNode.parent == newNode.parent.parent.left) {
Node uncle = newNode.parent.parent.right;
if (uncle.color == Color.RED) {
newNode.parent.color = Color.BLACK;
uncle.color = Color.BLACK;
newNode.parent.parent.color = Color.RED;
newNode = newNode.parent.parent;
} else {
if (newNode == newNode.parent.right) {
newNode = newNode.parent;
leftRotate(newNode);
}
newNode.parent.color = Color.BLACK;
newNode.parent.parent.color = Color.RED;
rightRotate(newNode.parent.parent);
}
} else {
Node uncle = newNode.parent.parent.left;
if (uncle.color == Color.RED) {
newNode.parent.color = Color.BLACK;
uncle.color = Color.BLACK;
newNode.parent.parent.color = Color.RED;
newNode = newNode.parent.parent;
} else {
if (newNode == newNode.parent.left) {
newNode = newNode.parent;
rightRotate(newNode);
}
newNode.parent.color = Color.BLACK;
newNode.parent.parent.color = Color.RED;
leftRotate(newNode.parent.parent);
}
}
}
root.color = Color.BLACK;
}
// Left Rotation
private void leftRotate(Node x) {
Node y = x.right;
x.right = y.left;
if (y.left != nil) {
y.left.parent = x;
}
y.parent = x.parent;
if (x.parent == nil) {
root = y;
} else if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
y.left = x;
x.parent = y;
}
// Right Rotation
private void rightRotate(Node y) {
Node x = y.left;
y.left = x.right;
if (x.right != nil) {
x.right.parent = y;
}
x.parent = y.parent;
if (y.parent == nil) {
root = x;
} else if (y == y.parent.right) {
y.parent.right = x;
} else {
y.parent.left = x;
}
x.right = y;
y.parent = x;
}
// Other Red-Black Tree methods...
}
#3 Insertion in a 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 key;
char color; // 'R' for red, 'B' for black
struct Node* parent;
struct Node* left;
struct Node* right;
} Node;
// Function to perform left rotation
void leftRotate(Node** root, Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left != NULL)
y->left->parent = x;
y->parent = x->parent;
if (x->parent == NULL)
*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(Node** root, Node* y) {
Node* x = y->left;
y->left = x->right;
if (x->right != NULL)
x->right->parent = y;
x->parent = y->parent;
if (y->parent == NULL)
*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 fix the Red-Black Tree properties after insertion
void fixInsert(Node** root, Node* z) {
while (z != *root && z->parent->color == 'R') {
if (z->parent == z->parent->parent->left) {
Node* y = z->parent->parent->right;
if (y != NULL && 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(root, z);
}
z->parent->color = 'B';
z->parent->parent->color = 'R';
rightRotate(root, z->parent->parent);
}
} else {
// Symmetric case (left is replaced with right)
Node* y = z->parent->parent->left;
if (y != NULL && 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(root, z);
}
z->parent->color = 'B';
z->parent->parent->color = 'R';
leftRotate(root, z->parent->parent);
}
}
}
(*root)->color = 'B';
}
// Function to insert a key into Red-Black Tree
void insertRBTree(Node** root, int key) {
// Create a new node
Node* z = (Node*)malloc(sizeof(Node));
z->key = key;
z->left = z->right = z->parent = NULL;
z->color = 'R';
// BST insert
Node* y = NULL;
Node* x = *root;
while (x != NULL) {
y = x;
if (z->key < x->key)
x = x->left;
else
x = x->right;
}
z->parent = y;
if (y == NULL)
*root = z;
else if (z->key < y->key)
y->left = z;
else
y->right = z;
// Fix Red-Black Tree properties
fixInsert(root, z);
}
// Function to print Red-Black Tree in-order
void inOrderTraversal(Node* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("(%d, %c) ", root->key, root->color);
inOrderTraversal(root->right);
}
}
// Function to free memory allocated for Red-Black Tree
void freeRBTree(Node* root) {
if (root != NULL) {
freeRBTree(root->left);
freeRBTree(root->right);
free(root);
}
}
int main() {
Node* root = NULL;
// Insert keys into Red-Black Tree
int keys[] = {7, 3, 18, 10, 22, 8, 11, 26};
int n = sizeof(keys) / sizeof(keys[0]);
for (int i = 0; i < n; i++) {
insertRBTree(&root, keys[i]);
printf("Inserted %d: In-order Traversal: ", keys[i]);
inOrderTraversal(root);
printf("\n");
}
// Free memory
freeRBTree(root);
return 0;
}
#4 Insertion in a 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;
Node* left;
Node* right;
Node(T val) : data(val), 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>* x);
void insertFixup(Node* z);
public:
RedBlackTree() : root(nullptr) {}
// Public function to insert a value into the Red-Black Tree
void insert(T val);
};
// Left rotation in the Red-Black Tree
template < typename T>
void RedBlackTree::leftRotate(Node* x) {
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;
}
// Right rotation in the Red-Black Tree
template < typename T>
void RedBlackTree::rightRotate(Node* x) {
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->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->right = x;
x->parent = y;
}
// Fix the Red-Black Tree properties after inserting a node
template < typename T>
void RedBlackTree::insertFixup(Node* z) {
while (z->parent != nullptr && z->parent->color == RED) {
if (z->parent == z->parent->parent->left) {
Node* y = z->parent->parent->right;
if (y != nullptr && 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;
leftRotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rightRotate(z->parent->parent);
}
} else {
Node < T>* y = z->parent->parent->left;
if (y != nullptr && 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;
rightRotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
leftRotate(z->parent->parent);
}
}
}
root->color = BLACK;
}
// Public function to insert a value into the Red-Black Tree
template < typename T>
void RedBlackTree::insert(T val) {
Node* z = new Node(val);
Node* y = nullptr;
Node < T>* x = root;
while (x != nullptr) {
y = x;
if (z->data < x->data) {
x = x->left;
} else {
x = x->right;
}
}
z->parent = y;
if (y == nullptr) {
root = z;
} else if (z->data < y->data) {
y->left = z;
} else {
y->right = z;
}
insertFixup(z);
}
int main() {
RedBlackTree < int> rbt;
// Inserting values into the Red-Black Tree
rbt.insert(10);
rbt.insert(20);
rbt.insert(30);
rbt.insert(15);
rbt.insert(25);
// You can perform other operations on the Red-Black Tree as needed
return 0;
}
Demonstration
Insertion in a Red-Black Tree-DevsEnv