Lesson 2
Today we'll meet our first self-balancing BST!
After today's lesson, you should be able to explain how 2–3–4 and Red–Black trees maintain balance. You should also be able to model insertion in 2–3–4 and Red–Black trees.
This lesson will be relevant to the following learning goals in Group 8:
- Goal 8C: 2–3–4 and Red–Black Trees:
- Explain how 2–3–4 and red–black trees maintain balance.
- Goal 8D: BST Complexity:
- Use asymptotic complexity terminology to describe the cost of insert and lookup for
- Randomized BSTs
- 2–3–4 trees
- Red–Black trees
- Splay trees
- Discuss the implications of those costs for usage.
Outline
- Before You Start…
- Relaxing a Constraint: Multiple Types of Nodes
- Insertion in 2–3–4 Trees
- Complexity of 2–3–4 Trees
- Super Edges
- Red–Black Trees
This is a pretty good spot for a break before we get into the weeds of red–black trees.
- Rearranging BSTs with Rotations
- Red–Black Tree Insert
- Complexity and Applications of Red–Black Trees
- Key Points
- Before You Go…
To receive credit: complete all pages above, then this page will be complete as well (and get a green check emoji at the bottom right of the page).
(When logged in, completion status appears here.)