Red-Black Tree Implementation in Java

A Red-Black Tree is a self-balancing binary search tree where each node contains an extra bit for denoting the color of the node, either red or black. The tree maintains balance by ensuring that no two consecutive red nodes exist on any path from the root to a leaf and that the number of black nodes is the same on all such paths.

Program Structure

The implementation of a Red-Black Tree involves two main classes:

• Node: Represents a node in the Red-Black Tree.
• RedBlackTree: Manages the Red-Black Tree operations such as insertion, balancing, and rotations.

Node Class

This class represents a node in the Red-Black Tree. Each node contains:

• An integer value key.
• A reference to the left child node.
• A reference to the right child node.
• A reference to the parent node.
• A boolean color to represent the color of the node (red or black).

RedBlackTree Class

This class encapsulates the Red-Black Tree operations and contains the following components:

• insert: Inserts a node into the Red-Black Tree while maintaining balance.
• rotateLeft: Performs a left rotation to restore balance.
• rotateRight: Performs a right rotation to restore balance.
• fixInsertion: Fixes any violations after insertion to maintain Red-Black Tree properties.
• preOrder: Performs a pre-order traversal of the tree.

Java Code Implementation

Node Class


class Node {
int key;
Node left, right, parent;
boolean color;

public Node(int key) {
this.key = key;
left = right = parent = null;
color = true; // New nodes are red by default
}
}

RedBlackTree Class


class RedBlackTree {
private Node root;
private Node TNULL;

public RedBlackTree() {
TNULL = new Node(0);
TNULL.color = false;
root = TNULL;
}

private void rotateLeft(Node x) {
Node y = x.right;
x.right = y.left;
if (y.left != TNULL) {
y.left.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
this.root = y;
} else if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
y.left = x;
x.parent = y;
}

private void rotateRight(Node x) {
Node y = x.left;
x.left = y.right;
if (y.right != TNULL) {
y.right.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
this.root = y;
} else if (x == x.parent.right) {
x.parent.right = y;
} else {
x.parent.left = y;
}
y.right = x;
x.parent = y;
}

private void fixInsertion(Node k) {
Node u;
while (k.parent.color == true) {
if (k.parent == k.parent.parent.right) {
u = k.parent.parent.left;
if (u.color == true) {
u.color = false;
k.parent.color = false;
k.parent.parent.color = true;
k = k.parent.parent;
} else {
if (k == k.parent.left) {
k = k.parent;
rotateRight(k);
}
k.parent.color = false;
k.parent.parent.color = true;
rotateLeft(k.parent.parent);
}
} else {
u = k.parent.parent.right;
if (u.color == true) {
u.color = false;
k.parent.color = false;
k.parent.parent.color = true;
k = k.parent.parent;
} else {
if (k == k.parent.right) {
k = k.parent;
rotateLeft(k);
}
k.parent.color = false;
k.parent.parent.color = true;
rotateRight(k.parent.parent);
}
}
if (k == root) {
break;
}
}
root.color = false;
}

public void insert(int key) {
Node node = new Node(key);
node.parent = null;
node.left = TNULL;
node.right = TNULL;
node.color = true;

Node y = null;
Node x = this.root;

while (x != TNULL) {
y = x;
if (node.key < x.key) {
x = x.left;
} else {
x = x.right;
}
}

node.parent = y;
if (y == null) {
root = node;
} else if (node.key < y.key) {
y.left = node;
} else {
y.right = node;
}

if (node.parent == null) {
node.color = false;
return;
}

if (node.parent.parent == null) {
return;
}

fixInsertion(node);
}

public void preOrder(Node node) {
if (node != TNULL) {
System.out.print(node.key + ” “);
preOrder(node.left);
preOrder(node.right);
}
}
}

Explanation

Here is a detailed explanation of the key components in the Red-Black Tree implementation:

1. Node Class

This class represents a node in the Red-Black Tree. Each node contains a key (value), references to its left and right children, a reference to its parent, and a boolean color (where true represents red and false represents black). Nodes are initially colored red when inserted.

2. rotateLeft Method

The rotateLeft method performs a left rotation to restore balance in the Red-Black Tree. This is typically done when the right child of a node is red and its left child is black, causing the tree to be right-heavy.

3. rotateRight Method

The rotateRight method performs a right rotation to restore balance in the Red-Black Tree. This is typically done when the left child of a node is red and its right child is black, causing the tree to be left-heavy.

4. fixInsertion Method

The fixInsertion method is called after inserting a new node to fix any violations of the Red-Black Tree properties. The method uses rotations and recoloring to maintain the tree’s balance and properties. The main properties that must be maintained are:

• 1. The root is always black.
• 2. Red nodes cannot have red children.
• 3. Every path from the root to a leaf must have the same number of black nodes.

5. insert Method

The insert method inserts a new node into the Red-Black Tree while maintaining its balance. After inserting the node, the fixInsertion method is called to ensure the tree remains balanced and adheres to Red-Black Tree properties.

6. preOrder Method

The preOrder method performs a pre-order traversal of the Red-Black Tree, printing the key of each node. This method can be used to verify the structure of the tree after various operations.

Conclusion

This Java implementation of a Red-Black Tree provides a self-balancing binary search tree that ensures O(log n) time complexity for insertion, deletion, and lookup operations. The Red-Black Tree maintains its balance through rotations and recoloring, ensuring efficient performance even in the worst-case scenarios.