WikiGalaxy
Red-Black Tree
Introduction to Red-Black Trees
A Red-Black Tree is a balanced binary search tree with an additional property that helps maintain the balance during insertions and deletions. Each node is colored either red or black, and the tree satisfies the following properties:
- The root is black.
- All leaves (NIL nodes) are black.
- If a node is red, both its children must be black.
- Every path from a node to its descendant NIL nodes has the same number of black nodes.
Insertion in Red-Black Tree
Step-by-Step Insertion
Insertion in a Red-Black Tree involves adding the node as a red node and then fixing any violations of the Red-Black properties. The main steps are:
- Insert the node as a red node.
- Fix any violations by recoloring and rotations.
class RedBlackTree {
private Node root;
// Define Node structure and other methods
void insert(int data) {
// Insert logic
fixViolations(newNode);
}
private void fixViolations(Node node) {
// Fix violations logic
}
}
Deletion in Red-Black Tree
Handling Deletion
Deletion in a Red-Black Tree is more complex than insertion. It involves removing the node and then fixing any property violations. The steps include:
- Remove the node.
- Fix any violations using rotations and recoloring.
class RedBlackTree {
private Node root;
// Define Node structure and other methods
void delete(int data) {
// Deletion logic
fixViolations(node);
}
private void fixViolations(Node node) {
// Fix violations logic
}
}
Balancing Through Rotations
Left and Right Rotations
Rotations are used in Red-Black Trees to maintain balance. There are two types of rotations:
- Left Rotation: Used when a right child is causing imbalance.
- Right Rotation: Used when a left child is causing imbalance.
class RedBlackTree {
private Node root;
// Define Node structure and other methods
void leftRotate(Node node) {
// Left rotation logic
}
void rightRotate(Node node) {
// Right rotation logic
}
}
Use Cases of Red-Black Trees
Applications in Computing
Red-Black Trees are widely used due to their balanced nature, which ensures operations like insertion, deletion, and search can be performed in O(log n) time. Some common applications include:
- Implementing associative arrays.
- Maintaining ordered data structures.
- Used in many libraries and systems, such as the Java Collections Framework.
