What are Red-Black Trees?
Red-Black Trees are self-balancing binary search trees with an extra bit of information per node: the color (red or black).
Properties of Red-Black Trees
- Every node is either red or black.
- The root is always black.
- Every leaf (NIL) is black.
- If a node is red, then both its children are black.
- For each node, all paths from the node to descendant leaves contain the same number of black nodes.
Red-Black Tree Visualization
Click on a node to delete it.
Rebalancing Algorithm
Rebalancing in a Red-Black Tree ensures that the tree remains balanced after insertion or deletion of nodes, maintaining efficient operation times. The rebalancing process involves a series of color changes and rotations based on specific cases.
- Case 1: The new node is the root.
Color the new node black. - Case 2: The parent of the new node is black.
No action needed as the tree remains balanced. - Case 3: Both the parent and the uncle of the new node are red.
Recolor the parent and uncle to black, and the grandparent to red. Then, continue fixing from the grandparent. - Case 4: The parent is red, the uncle is black, and the new node is a right child.
Perform a left rotation on the parent. - Case 5: The parent is red, the uncle is black, and the new node is a left child.
Perform a right rotation on the grandparent and swap the colors of the parent and grandparent.
These steps ensure that the Red-Black Tree properties are maintained, guaranteeing that the tree remains balanced with a height of O(log n), which allows for efficient search, insertion, and deletion operations.