Lesson 2
In this lesson we'll introduce another type of balanced tree.
This one you will actually implement!
This lesson will be relevant to the following learning goals in Group 8:
- Goal 8B: Random and Randomized Trees:
- Explain how random and randomized 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
- Randomly Generated BSTs
- Expected Complexity of Randomly Generated BSTs
- Randomized Trees
- Analyzing Randomized Trees
This would be a good spot to take a break.
Nearly done. Maybe take a quick break here.
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.)