Red-Black Tree
Introduction to Red-Black Tree
A Red-Black Tree is a self-balancing binary search tree (BST) that ensures logarithmic height, making operations such as insertion, deletion, and search efficient. It is a type of binary search tree (BST) with additional properties that maintain balance while performing insertions and deletions.
Properties of Red-Black Tree
To maintain balance, a Red-Black Tree follows these five properties:
- Every node is either RED or BLACK.
- The root node is always BLACK.
- Every leaf node (NIL) is BLACK.
- If a node is RED, then both its children must be BLACK (No two consecutive RED nodes are allowed).
- For every path from a node to its descendant NIL nodes, the number of BLACK nodes must be the same (Black height property).
These properties ensure that no path in the tree is more than twice the length of the shortest path, keeping operations O(log n).
Need for Red-Black Tree
- BST can become skewed (leading to O(n) operations in the worst case).
- AVL Trees maintain strict balance, but require frequent rotations, making insertions and deletions slower.
- Red-Black Trees balance the need for efficiency and balance, ensuring O(log n) operations for insertion, deletion, and search with fewer rotations compared to AVL Trees.
Example Red-Black Tree
Consider the following Red-Black Tree:
Explanation:
- Root (20) is BLACK → Property 2 is satisfied.
- Each node is either RED or BLACK → Property 1 is satisfied.
- Every leaf (NIL) is BLACK (implicit NIL leaves are not shown).
- No two consecutive RED nodes exist (15R and 25R are RED, but their children are BLACK) → Property 4 is satisfied.
- Every path from root to a NIL leaf contains the same number of BLACK nodes (For all paths, Black height = 2) → Property 5 is satisfied.
This tree follows all the Red-Black Tree properties, making it balanced and efficient.
What is a NIL Leaf Node in a Red-Black Tree?
In a Red-Black Tree, every leaf node is a special node called a NIL node. These are BLACK-colored sentinel nodes that represent the absence of a child. NIL nodes help maintain balance properties in the tree by ensuring that all paths from the root to the leaves have the same number of BLACK nodes (Black Height Property).
Consider the following Red-Black Tree:
(30B)
/ \
(20R) (40R)
/ \ \
(10B) (25B) (50B)
/ \ / \ / \
NIL NIL NIL NIL NIL NIL
- The NIL nodes (represented as
NIL) are BLACK and serve as leaf nodes. - Each NIL node is a child of a real node but does not contain any value.
- The Black Height Property holds because all paths from the root to any NIL node have the same number of BLACK nodes.
