Group 8: Trees
This group of topics relate to binary search trees.
In CS 70, we get to see several cool self-balancing trees. Understanding how they work will help us reason about the trade-offs between different data structures!
Topics
You will know that you have achieved this group of learning objectives when you are able to
- Goal 8A: Binary Search Trees:
- Use tree terminology (size, height, root, node, edge, leaf) to characterize binary search trees.
- Goal 8B: Random and Randomized Trees:
- Explain how random and randomized trees maintain balance.
- 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.
- Use asymptotic complexity terminology to describe the cost of insert and lookup for
Need More Practice?
This group of goals are addressed in the following places:
- Week 9 Lesson 1 (Goal 8A, Goal 8D)
- Week 9 Lesson 2 (Goal 8C, Goal 8D)
- Week 10 Lesson 1 (Goal 8D)
- Week 10 Lesson 2 (Goal 8B, Goal 8D)
(When logged in, completion status appears here.)