Lesson 1
Today we'll learn about a new kind of complexity analysis called amortized analysis. It is useful for understanding structures that permit efficient operations, but occasionally perform expensive maintenance or re-organization operations.
We'll also see yet another type of self-balancing tree called a splay tree which takes advantage of amortization.
This lesson will address aspects of the following learning goals from Group 7 and Group 8:
- Goal 7D: Amortized Bounds:
- Explain the meaning of an amortized complexity bound.
- 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.
- Use asymptotic complexity terminology to describe the cost of insert and lookup for
Outline
- Before You Start…
- Motivating Example: Network Routing
- Splay Trees
- Splay Tree Complexity (Initial Exploration)
This is a good time to take a quick break!
- Operation Cost That Varies: Our In-Order Iterators
- Characterizing Operation Cost That Varies
- Amortization Example:
IntVector push_back - Amortization Approaches
You could take a break here, too.
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.)