Red-Black Tree
A self-balancing binary search tree where each node is colored red or black, ensuring the tree remains approximately balanced during insertions and deletions.
Ready
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Standard BSTs can degrade into linked lists (O(n)) with sorted input. AVL trees are strictly balanced but require frequent rotations. Red-Black trees trade some balance for faster insertion/deletion (fewer rotations), guaranteeing O(log n) operations while maintaining a height at most 2 * log(n+1).
Concept
A Red-Black Tree is a BST with 5 properties:
- Nodes are Red or Black.
- Root is always Black.
- Leaves (NIL) are Black.
- If a node is Red, both children are Black (no double reds).
- Every path from a node to its descendant NIL nodes has the same number of Black nodes.
How it Works
- Insertion: Insert like BST (red node). Fix violations (recoloring or rotation) if parent is also red.
- Deletion: Complex. If a black node is deleted, tree height reduces, violating black-height. Requires restructuring.
- Rotations: Left and Right rotations are used to rebalance.
- Recoloring: Changing node colors to fix parent-child conflicts.
Step-by-Step Breakdown
Insertion Logic:
- Insert node as RED.
- If parent is Black: Done.
- If parent is Red: Check uncle's color.
- Uncle Red: Recolor Parent+Uncle Black, Grandparent Red. Repeat for GP.
- Uncle Black: Rotate (LL, RR, LR, RL cases) and recolor.
When to Use
- General purpose self-balancing tree (used in C++ `std::map`, Java `TreeMap`).
- When insertions/deletions are frequent (faster than AVL).
- Implementing associative arrays.
When NOT to Use
- When lookups are the dominant operation (AVL is strictly balanced, so slightly faster lookups).
- Simple scenarios where O(n) is acceptable.
How to Identify
Keywords: "Map Implementation", "Self-Balancing", "Associative Array", "Ordered Set".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.