In computer science, a red-black tree is a type of self-balancing binary search tree. It is a data structure used to store and manage data efficiently. It is one of the most popular data structures in the world, used in many applications. Red-black trees are popular because of their efficient search, insert, delete, and update operations. They are also relatively easy to implement and maintain.
In this article, we’ll discuss how red-black trees work, their time complexity for access, search, insertion, and deletion, and their space complexity. We’ll also provide Java code samples throughout to illustrate each topic.
What Is a Red-Black Tree?
A red-black tree is a type of binary search tree, which means it has two children for each node: a left child and a right child. The left child is always less than its parent, and the right child is always greater than its parent.
In a red-black tree, each node also has a color, which can be either red or black. The color of a node is determined by its parent’s color and the colors of its children. A node can have up to two children, so it can have up to three colors: red, black, or a combination of the two.
Red-black trees are self-balancing, which means they maintain a certain level of balance as data is inserted and deleted. This makes them efficient for searching, inserting, deleting, and updating data.
Properties of Red-Black Trees
Red-black trees have certain properties that make them efficient for searching, inserting, deleting, and updating data. These properties are:
- Every node is either red or black.
- The root node is always black.
- All leaf nodes (null nodes) are black.
- All red nodes must have two black children.
- Every path from the root to a leaf must contain the same number of black nodes.
These properties ensure that the tree is balanced and that data can be efficiently inserted, deleted, and updated.
Time Complexity
The time complexity of a red-black tree is dependent on the number of nodes in the tree. The average time complexity for searching, insertion, deletion, and update operations is O(log n), where n is the number of nodes in the tree. The worst-case time complexity for these operations is O(n).
Space Complexity
The space complexity of a red-black tree is O(n), where n is the number of nodes in the tree. This means that the tree uses O(n) space to store data, regardless of the size of the data.
Java Code
Now, let’s look at some Java code to illustrate how a red-black tree works.
// Node class to represent a node in a red-black tree
class Node {
int data;
Node left, right;
Color color;
Node(int data) {
this.data = data;
left = right = null;
color = Color.RED;
}
}
// Enum to represent the color of a node
enum Color {
RED, BLACK;
}
// Class to represent a red-black tree
class RedBlackTree {
Node root;
RedBlackTree() {
root = null;
}
// Insert a node into the tree
void insert(int data) {
root = insertNode(root, data);
}
// Recursive function to insert a node into the tree
private Node insertNode(Node node, int data) {
// If the tree is empty, create a new node and set it as the root
if (node == null) {
node = new Node(data);
}
// If the data is smaller than the node, go left
else if (data < node.data) {
node.left = insertNode(node.left, data);
}
// If the data is greater than the node, go right
else if (data > node.data) {
node.right = insertNode(node.right, data);
}
// Set the color of the node
node.color = Color.RED;
// Return the node
return node;
}
// Search for a node in the tree
boolean search(int data) {
return searchNode(root, data);
}
// Recursive function to search for a node in the tree
private boolean searchNode(Node node, int data) {
// If the tree is empty, return false
if (node == null) {
return false;
}
// If the data is smaller than the node, go left
if (data < node.data) {
return searchNode(node.left, data);
}
// If the data is greater than the node, go right
else if (data > node.data) {
return searchNode(node.right, data);
}
// If the data is equal to the node, return true
else {
return true;
}
}
// Delete a node from the tree
void delete(int data) {
root = deleteNode(root, data);
}
// Recursive function to delete a node from the tree
private Node deleteNode(Node node, int data) {
// If the tree is empty, return null
if (node == null) {
return null;
}
// If the data is smaller than the node, go left
if (data < node.data) {
node.left = deleteNode(node.left, data);
}
// If the data is greater than the node, go right
else if (data > node.data) {
node.right = deleteNode(node.right, data);
}
// If the data is equal to the node, delete the node
else {
// If the node is a leaf node, set it to null
if (node.left == null && node.right == null) {
node = null;
}
// If the node has one child, set it to the child
else if (node.left == null) {
node = node.right;
}
else if (node.right == null) {
node = node.left;
}
// If the node has two children, replace it with its in-order successor
else {
Node successor = findMin(node.right);
node.data = successor.data;
node.right = deleteNode(node.right, successor.data);
}
}
// Set the color of the node
node.color = Color.BLACK;
// Return the node
return node;
}
// Find the in-order successor of a node
private Node findMin(Node node) {
// If the tree is empty, return null
if (node == null) {
return null;
}
// If the node has no left child, it is the in-order successor
if (node.left == null) {
return node;
}
// Otherwise, go left
return findMin(node.left);
}
}
Conclusion
Red-black trees are a type of self-balancing binary search tree. They are popular because they maintain a certain level of balance as data is inserted and deleted, making them efficient for searching, inserting, deleting, and updating data. Their time complexity for access, search, insertion, and deletion is O(log n) on average and O(n) in the worst case. Their space complexity is O(n).
Exercises
Write a method to check if a given red-black tree is valid.
public static boolean isValidRedBlackTree(Node root) {
if (root == null) {
return true;
}
// Check if root is black
if (root.color != Color.BLACK) {
return false;
}
// Check if all red nodes have two black children
if (!checkRedNodeProperties(root)) {
return false;
}
// Check if all paths from root to leaves have same number of black nodes
int blackNodesCount = getBlackNodesCount(root);
if (!checkBlackNodesCount(root, blackNodesCount)) {
return false;
}
return true;
}
private static boolean checkRedNodeProperties(Node node) {
if (node == null) {
return true;
}
if (node.color == Color.RED &&
(node.left == null || node.left.color != Color.BLACK) &&
(node.right == null || node.right.color != Color.BLACK)) {
return false;
}
return checkRedNodeProperties(node.left) && checkRedNodeProperties(node.right);
}
private static int getBlackNodesCount(Node node) {
if (node == null) {
return 0;
}
if (node.color == Color.BLACK) {
return 1 + getBlackNodesCount(node.left) + getBlackNodesCount(node.right);
} else {
return getBlackNodesCount(node.left) + getBlackNodesCount(node.right);
}
}
private static boolean checkBlackNodesCount(Node node, int blackNodesCount) {
if (node == null) {
return true;
}
if (node.color == Color.BLACK) {
blackNodesCount--;
}
if (blackNodesCount != getBlackNodesCount(node.left) ||
blackNodesCount != getBlackNodesCount(node.right)) {
return false;
}
return checkBlackNodesCount(node.left, blackNodesCount) &&
checkBlackNodesCount(node.right, blackNodesCount);
}
Write a method to insert a node into a red-black tree.
public static Node insertNode(Node root, int data) {
if (root == null) {
// Create a new node and set it as the root
root = new Node(data);
root.color = Color.BLACK;
} else if (data < root.data) {
// If the data is smaller than the node, go left
root.left = insertNode(root.left, data);
} else if (data > root.data) {
// If the data is greater than the node, go right
root.right = insertNode(root.right, data);
} else {
// If the data is equal to the node, do nothing
return root;
}
// Check if the node needs to be balanced
return balanceTree(root);
}
Write a method to search for a node in a red-black tree.
public static boolean searchNode(Node node, int data) {
if (node == null) {
// If the tree is empty, return false
return false;
} else if (data < node.data) {
// If the data is smaller than the node, go left
return searchNode(node.left, data);
} else if (data > node.data) {
// If the data is greater than the node, go right
return searchNode(node.right, data);
} else {
// If the data is equal to the node, return true
return true;
}
}
Write a method to delete a node from a red-black tree.
public static Node deleteNode(Node node, int data) {
if (node == null) {
// If the tree is empty, return null
return null;
} else if (data < node.data) {
// If the data is smaller than the node, go left
node.left = deleteNode(node.left, data);
} else if (data > node.data) {
// If the data is greater than the node, go right
node.right = deleteNode(node.right, data);
} else {
// If the data is equal to the node, delete the node
if (node.left == null && node.right == null) {
// If the node is a leaf node, set it to null
node = null;
} else if (node.left == null) {
// If the node has one child, set it to the child
node = node.right;
} else if (node.right == null) {
// If the node has one child, set it to the child
node = node.left;
} else {
// If the node has two children, replace it with its in-order successor
Node successor = findMin(node.right);
node.data = successor.data;
node.right = deleteNode(node.right, successor.data);
}
}
// Check if the node needs to be balanced
return balanceTree(node);
}
Write a method to find the in-order successor of a node in a red-black tree.
public static Node findMin(Node node) {
// If the tree is empty, return null
if (node == null) {
return null;
}
// If the node has no left child, it is the in-order successor
if (node.left == null) {
return node;
}
// Otherwise, go left
return findMin(node.left);
}