Red-Black Tree Code Implementations
Production-ready Red-Black Tree data structure implementations in C++, Python, Java, and JavaScript on AntInLoop.
Study Red-Black Tree Guide ยท Launch Visualizer
CPP Implementation
#include<bits/stdc++.h>
using namespace std;
// A Node of the doubly linked list
struct Node
{
int data; // data part
Node *left, *right; // left and right pointers
int color; // color of the node, 0 for black, 1 for red
};
// Function to create a new node
Node* newNode(int data)
{
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
node->color = 1; // new nodes are initially red
return node;
}
// Function to perform left-rotation
void rotateLeft(Node *&root, Node *&pt)
{
Node *pt_right = pt->right;
pt->right = pt_right->left;
if (pt->right != NULL)
pt->right->parent = pt;
pt_right->parent = pt->parent;
if (pt->parent == NULL)
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;
}
// Function to perform right-rotation
void rotateRight(Node *&root, Node *&pt)
{
Node *pt_left = pt->left;
pt->left = pt_left->right;
if (pt->left != NULL)
pt->left->parent = pt;
pt_left->parent = pt->parent;
if (pt->parent == NULL)
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;
}
// Function to fix violations caused during insertion
void fixViolation(Node *&root, Node *&pt)
{
Node *parent_pt = NULL;
Node *grand_parent_pt = NULL;
while ((pt != root) && (pt->color != 0) && (pt->parent->color == 1))
{
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 != NULL && uncle_pt->color == 1)
{
grand_parent_pt->color = 1;
parent_pt->color = 0;
uncle_pt->color = 0;
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 != NULL) && (uncle_pt->color == 1))
{
grand_parent_pt->color = 1;
parent_pt->color = 0;
uncle_pt->color = 0;
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 = 0;
}
// Function to insert a new node with given data
void insert(Node *&root, int data)
{
Node *pt = newNode(data);
root = insertBST(root, pt);
fixViolation(root, pt);
}
// Function to do inorder and level order traversals
void inorder(Node *trav)
{
if (trav == NULL)
return;
inorder(trav->left);
cout << trav->data << " ";
inorder(trav->right);
}
// Driver Code
int main()
{
Node *root = NULL;
insert(root, 7);
insert(root, 6);
insert(root, 5);
insert(root, 4);
insert(root, 3);
insert(root, 2);
insert(root, 1);
cout << "Inorder Traversal of Created Tree\n";
inorder(root);
cout << "\n";
return 0;
}JAVA Implementation
// Red-Black Tree Implementation in Java
class RedBlackTree {
// Define node colors
private static final boolean RED = true;
private static final boolean BLACK = false;
// Node structure
static class Node {
int data;
Node left, right, parent;
boolean color;
Node(int data) {
this.data = data;
this.color = RED; // new node is always RED initially
}
}
private Node root;
// Left rotate
private void leftRotate(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;
}
// Right rotate
private void rightRotate(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;
}
// Fix violations after insertion
private void fixInsert(Node z) {
while (z.parent != null && z.parent.color == RED) {
if (z.parent == z.parent.parent.left) {
Node y = z.parent.parent.right;
if (y != null && y.color == RED) {
// Case 1: Uncle is RED
z.parent.color = BLACK;
y.color = BLACK;
z.parent.parent.color = RED;
z = z.parent.parent;
} else {
// Case 2 & 3: Uncle is BLACK
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 y = z.parent.parent.left;
if (y != null && y.color == RED) {
// Case 1: Uncle is RED
z.parent.color = BLACK;
y.color = BLACK;
z.parent.parent.color = RED;
z = z.parent.parent;
} else {
// Case 2 & 3: Uncle is BLACK
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; // Root must always be BLACK
}
// Insert a new node
public void insert(int data) {
Node z = new Node(data);
Node y = null;
Node x = root;
while (x != null) {
y = x;
if (z.data < x.data) {
x = x.left;
} else {
x = x.right;
}
}
z.parent = y;
if (y == null) {
root = z;
} else if (z.data < y.data) {
y.left = z;
} else {
y.right = z;
}
fixInsert(z);
}
// Search a value
public boolean search(int data) {
Node node = root;
while (node != null) {
if (data == node.data) return true;
if (data < node.data) node = node.left;
else node = node.right;
}
return false;
}
// Inorder Traversal
public void inorder(Node node) {
if (node == null) return;
inorder(node.left);
System.out.print(node.data + (node.color == RED ? "(R) " : "(B) "));
inorder(node.right);
}
public void inorder() {
inorder(root);
System.out.println();
}
// Main method
public static void main(String[] args) {
RedBlackTree rbt = new RedBlackTree();
int[] values = {10, 20, 30, 15, 25, 5, 1};
for (int val : values) {
rbt.insert(val);
System.out.print("Inorder after inserting " + val + ": ");
rbt.inorder();
}
System.out.println("Search 15: " + (rbt.search(15) ? "Found" : "Not Found"));
System.out.println("Search 50: " + (rbt.search(50) ? "Found" : "Not Found"));
}
}