Senior LevelData Structures & Algorithms
What are the properties of a Red-Black Tree and why is it preferred over AVL?
ā Interview Prompt: Explain Red-Black Tree invariants, O(log N) operations, comparison to AVL trees (rotation count), and real-world usage.
A Red-Black Tree is a self-balancing BST with these invariants:
1
Every node is Red or Black.
2
Root is Black.
3
Every leaf (NIL) is Black.
4
Red nodes have Black children (no two consecutive reds).
5
Every path from root to NIL has the same number of Black nodes (Black-height).
Red-Black vs AVL:
| | AVL | Red-Black |
|---|---|---|
| Balance | Stricter (|BF| ā¤ 1) | Looser (2Ć height ratio) |
| Rotations per insert/delete | More | Fewer (~2 max per operation) |
| Read-heavy | Slightly faster lookups | Slightly slower |
| Write-heavy | Slower | Faster |
Usage: C++ std::map, Java TreeMap, Linux kernel's CFS scheduler.
Code Implementation Example
markdown
Red-Black Tree Insert Invariant Repair Cases:
Case 1: Uncle is RED ā Recolor parent, uncle black; grandparent red
Case 2: Uncle is BLACK, node is inner child ā Rotate parent
Case 3: Uncle is BLACK, node is outer child ā Rotate grandparent + recolor
B(GP) B(Parent)
/ / R(P) B(U) ā R(GP) R(Child)
R(Child)š”Red-Black Tree insertion repair cases ā at most 2 rotations.
šÆ Interview Key Takeaway
Red-Black Trees tolerate looser balance than AVL but perform fewer rotations on insert/delete. Preferred in write-heavy production systems (databases, OS schedulers).
#DSA#Red-Black Tree#Self-Balancing BST#Advanced#Senior
Back to all Data Structures & Algorithms Questionsā