The uncle in a Red-Black Tree is not explicitly mentioned in the five core Red-Black Tree properties, but it plays a crucial implicit role during insertion fix-up operations.
Let’s clarify:
🔸 Red-Black Tree Properties (Standard 5 Rules):
- Every node is either red or black.
- The root is always black.
- All leaves (NIL nodes) are black.
- If a node is red, then both its children must be black (no two red nodes in a row).
- Every path from a node to its descendant NIL nodes contains the same number of black nodes (black-height).
🔸 So, is the Uncle Rule part of the official properties?
No. There is no official property that says:
“If a node has a red parent, then its uncle must be black.”
This is not enforced as a standalone property — but it is implicitly addressed during the insertion fix-up process, to maintain Property 4 (no two consecutive red nodes).
✅ Uncle’s Role in Insertion Fix-up
The uncle node becomes important only when the parent is red, and it helps us decide between two fix-up strategies:
Case 1: Uncle is RED
👉 Perform recoloring
- Parent → Black
- Uncle → Black
- Grandparent → Red
Then move up and repeat fix-up if needed.
Case 2: Uncle is BLACK or NULL
👉 Perform rotation and recoloring to fix red-red violations.
📝 Conclusion:
✅ Uncle is not mentioned as a Red-Black Tree property,
❗But uncle’s color is critical in deciding what to do during insertion (and deletion) fix-up.
⚙️ So, the “uncle rule” is a practical concept used in algorithms, not a formal property.