A Red-Black Tree is a self-balancing binary search tree in which every node has a color attribute, with the value being either "red" or "black". The following is a visual representation of a Red-Black Tree:
Each node of a Red-Black Tree has the following attributes:
A Red-Black Tree has the following properties:
The following is an example of a Red-Black Tree that does not satisfy Property 5 (Red-Black Property):
As you can see, the node with key 4 is red, but its left child is also red. This violates Property 5.
Now that we've seen what a Red-Black Tree is, let's take a look at how they are used.
Red-Black Trees are used in a variety of applications, such as:
Now that we've seen what a Red-Black Tree is and some of the applications they are used in, let's take a look at how they are implemented.
First, we need to create a Node class. This class will store the key, color, left child, right child, and parent of a node.
public class Node {
int key;
boolean color;
Node leftChild;
Node rightChild;
Node parent;
public Node(int key, boolean color, Node leftChild, Node rightChild, Node parent) {
this.key = key;
this.color = color;
this.leftChild = leftChild;
this.rightChild = rightChild;
this.parent = parent;
}
}
Next, we need to create a Tree class. This class will store the root node of the tree.
public class Tree {
Node root;
public Tree() {
this.root = null;
}
}
Now that we have a Node class and a Tree class, we can start implementing the Red-Black Tree. The first operation we'll implement is the insert operation.
To insert a node into a Red-Black Tree, we first need to find the correct place to insert it. We do this by using the binary search tree insert algorithm. Once we've found the correct place to insert the node, we need to set the node's color to red. Then, we need to check if the tree is still valid. If the tree is not valid, we need to fix it.
The following is the insert algorithm:
public void insert(int key) {
// Create a new node with the given key and color it red
Node newNode = new Node(key, true, null, null, null);
// Find the correct place to insert the new node
Node currentNode = root;
Node parentNode = null;
while (currentNode != null) {
parentNode = currentNode;
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
} else {
currentNode = currentNode.rightChild;
}
}
// Set the new node's parent
newNode.parent = parentNode;
// Insert the new node into the tree
if (parentNode == null) {
// The new node is the root node
root = newNode;
} else if (key < parentNode.key) {
// The new node is the left child of the parent node
parentNode.leftChild = newNode;
} else {
// The new node is the right child of the parent node
parentNode.rightChild = newNode;
}
// Fix the tree
fixTree(newNode);
}
Now that we've seen how to insert a node into a Red-Black Tree, let's take a look at how to fix the tree.
There are four cases we need to consider when fixing a Red-Black Tree:
If the uncle is black, then we need to consider the orientation of the parent and node. If the parent and node are both left children or both right children, then we simply need to set the color of the parent to black and the color of the grandparent to red. Then, we need to recursively call the fixTree() method on the grandparent node.
If the parent and node are not both left children or both right children, then we need to perform a left rotation or right rotation. After the rotation, we need to set the color of the node to black and the color of the grandparent to red. Then, we need to recursively call the fixTree() method on the grandparent node.
If the uncle is black, then we need to consider the orientation of the parent and node. If the parent and node are both left children or both right children, then we need to set the color of the parent to black. Then, we need to recursively call the fixTree() method on the parent node.
If the parent and node are not both left children or both right children, then we need to perform a left rotation or right rotation. After the rotation, we need to set the color of the grandparent to red. Then, we need to recursively call the fixTree() method on the grandparent node.
The following is the fixTree() algorithm:
public void fixTree(Node node) {
// Case 1 (Node is the root node)
if (node.parent == null) {
node.color = false;
return;
}
// Case 2 (Node is a red node with a black parent)
if (node.color && !node.parent.color) {
return;
}
// Case 3 (Node is a red node with a red parent)
if (node.color && node.parent.color) {
Node uncle = getUncle(node);
if (uncle != null && uncle.color) {
// Set the colors of the node, parent, and uncle to black and the color of the grandparent to red
node.parent.color = false;
uncle.color = false;
getGrandparent(node).color = true;
// Recursively call the fixTree() method on the grandparent node
fixTree(getGrandparent(node));
} else {
// Perform a left rotation or right rotation
if (node == node.parent.rightChild && node.parent == getGrandparent(node).leftChild) {
// Perform a left rotation
leftRotate(node.parent);
// Set the colors of the node and parent to black and the color of the grandparent to red
node.color = false;
node.leftChild.color = true;
} else if (node == node.parent.leftChild && node.parent == getGrandparent(node).rightChild) {
// Perform a right rotation
rightRotate(node.parent);
// Set the colors of the node and parent to black and the color of the grandparent to red
node.color = false;
node.rightChild.color = true;
}
// Case 4 (Node is a black node with a red parent)
if (node == node.parent.leftChild) {
// Perform a right rotation
rightRotate(getGrandparent(node));
} else {
// Perform a left rotation
leftRotate(getGrandparent(node));
}
// Set the color of the grandparent to red
getGrandparent(node).color = true;
// Set the color of the parent to black
node.parent.color = false;
}
}
}
Now that we've seen how to fix a Red-Black Tree, let's take a look at how to perform a left rotation.
A left rotation is used to balance a tree when the right child of a node is heavier than the left child. The following is an example of a left rotation:
As you can see, the node that is being rotated is the node with key 3. The left child of this node is the node with key 2 and the right child is the node with key 4. After the rotation, the node with key 3 is the left child of the node with key 4 and the node with key 2 is the right child of the node with key 3.
The following is the leftRotate() algorithm:
public void leftRotate(Node node) {
// Check if the node has a right child
if (node.rightChild == null) {
return;
}
// Set the right child of the node to be the new root of the subtree
Node newRoot = node.rightChild;
// Set the left child of the new root to be the node's right child
newRoot.leftChild = node;
// Set the node's right child to be the new root's left child
node.rightChild = newRoot.leftChild;
// Set the new root's parent to be the node's parent
newRoot.parent = node.parent;
// Check if the node is the root node
if (node.parent == null) {
// Set the new root to be the root node
root = newRoot;
} else if (node == node.parent.leftChild) {
// Set the new root to be the node's left child
node.parent.leftChild = newRoot;
} else {
// Set the new root to be the node's right child
node.parent.rightChild = newRoot;
}
// Set the node's parent to be the new root
node.parent = newRoot;
}
Now that we've seen how to perform a left rotation, let's take a look at how to perform a right rotation.
A right rotation is used to balance a tree when the left child of a node is heavier than the right child. The following is an example of a right rotation:
As you can see, the node that is being rotated is the node with key 3. The left child of this node is the node with key 2 and the right child is the node with key 4. After the rotation, the node with key 3 is the right child of the node with key 2 and the node with key 4 is the left child of the node with key 3.
The following is the rightRotate() algorithm:
public void rightRotate(Node node) {
// Check if the node has a left child
if (node.leftChild == null) {
return;
}
// Set the left child of the node to be the new root of the subtree
Node newRoot = node.leftChild;
// Set the right child of the new root to be the node's left child
newRoot.rightChild = node;
// Set the node's left child to be the new root's right child
node.leftChild = newRoot.rightChild;
// Set the new root's parent to be the node's parent
newRoot.parent = node.parent;
// Check if the node is the root node
if (node.parent == null) {
// Set the new root to be the root node
root = newRoot;
} else if (node == node.parent.rightChild) {
// Set the new root to be the node's right child
node.parent.rightChild = newRoot;
} else {
// Set the new root to be the node's left child
node.parent.leftChild = newRoot;
}
// Set the node's parent to be the new root
node.parent = newRoot;
}
Now that we've seen how to perform a right rotation, let's take a look at how to delete a node from a Red-Black Tree.
To delete a node from a Red-Black Tree, we first need to find the node to delete. We do this by using the binary search tree delete algorithm. Once we've found the node to delete, we need to check if the tree is still valid. If the tree is not valid, we need to fix it.
The following is the delete algorithm:
public void delete(int key) {
// Find the node to delete
Node node = find(key);
// Check if the node was found
if (node == null) {
return;
}
// Delete the node
deleteNode(node);
}
Now that we've seen how to delete a node from a Red-Black Tree, let's take a look at how to delete a node.
There are three cases we need to consider when deleting a node from a Red-Black