A Red-Black Tree is a type of self-balancing binary search tree that ensures the height of the tree remains logarithmic. It was invented by Rudolf Bayer and named after their red-black color property.
Properties of a Red-Black Tree:
- 1. Every node is either red or black.
The root and leaves (NIL or null nodes) are black.
- 3. If a node is red, both its children are black.
- 4. Every path from a node to its descendant leaves contains the same number of black nodes.
These properties ensure that the longest path from the root to any leaf is no more than twice as long as the shortest path, which helps in maintaining a balanced tree structure.
When inserting a new node in a Red-Black Tree, it initially follows the same steps as inserting into a regular binary search tree. However, to maintain the properties of a Red-Black Tree, additional rules and rotations may be applied:
Rule 1: Coloring
All newly inserted nodes are initially colored red.
Rule 2: Property Violation
If the parent of the newly inserted node is also red, it violates property 3. In this case, further adjustments are required to restore balance:
- If both parent’s sibling and uncle are red, recolor parent, sibling, and uncle to black while coloring grandparent red.
- If parent’s sibling is black or null (NIL), perform appropriate rotations based on the relationship between the node, parent, and grandparent.
When deleting a node from a Red-Black Tree, it follows similar steps to deletion in a binary search tree. However, additional rules and rotations are applied to preserve the properties of the Red-Black Tree:
Rule 1: Case 1 – Node has no children
If the node to be deleted has no children (leaf), it can be simply removed.
Rule 2: Case 2 – Node has one child
If the node to be deleted has only one child, replace the node with its child.
Rule 3: Case 3 – Node has two children
If the node to be deleted has two children, find its successor (the smallest value in its right subtree) or predecessor (the largest value in its left subtree).
Note: The successor/predecessor will have at most one child if it exists.
- If the successor/predecessor is a leaf or has no children, remove it using case 1 or case 2.
- If the successor/predecessor has one child, replace it with that child using case 2.
A Red-Black Tree is an efficient self-balancing data structure used to store and retrieve elements while guaranteeing a logarithmic height. Its properties ensure that insertions and deletions can be performed while maintaining balance. Understanding Red-Black Trees is essential for optimizing search operations in various algorithms and applications.