Lesson 154
Red-Black Trees
Self-Balancing BST
1:00How five color rules turn an ordinary BST into a self-balancing tree with guaranteed O(log n) search, insert, and delete.
By the end, you can
- State and explain all five red-black tree color properties from memory.
- Identify which two rules (4 and 5) together enforce the O(log n) height bound.
- Compute the black-height of a small red-black tree.
- Explain why new nodes are always inserted as red rather than black.
- Describe the recolor fix-up (red uncle) and explain why it can bubble up the tree.
- Describe the rotation fix-up (black uncle) and explain why it is always final.
- State the maximum rotation counts for insert (2) and delete (3).
- Compare AVL trees and red-black trees and choose the right one for read-heavy vs write-heavy workloads.
Up next in Advanced Data Structures
