Advanced · Module 20 · Lesson 3 of 5
Red-black trees
A red-black tree colors each node red or black and requires every path from a node down to its leaves to cross the same number of black nodes. That looser rule keeps the height under 2 log₂ n while needing at most two rotations per insert and three per delete.
By the end you can
- State the red-black invariants and explain why they bound the height
- Fix a red-red violation after an insert by recoloring or rotating, depending on the uncle's color
- Compare red-black and AVL trees, and use the ordered-map operations that libraries build on them
Builds on AVL rotations.
01 · A question first
Java's TreeMap, C++'s std::map and the Linux kernel's scheduler all use the same balanced tree, and it isn't the most balanced one available. Red-black trees let some paths be twice as long as others. Why would the most widely used libraries choose a tree that is less balanced?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Balance by color
- Why that bounds the height
- Fixing an insert
- Red-black trees as 2-3-4 trees
- Red-black or AVL?
- Using an ordered map
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Something wrong with this lesson? Report a problem