Week 8 - Tree Wrapup and Hashing
Learning objectives
- Describe how a Treap uses the logic of a heap to balance a sorted tree
- Perform insertions on a Treap or Skip List
- Describe how to construct a hash function for various types of data
Class Schedule
Day 1
- Mixed review worksheet on self balancing trees. Then check this key
- Treaps and Skip Lists
Day 2
- Review for the midterm. See the study guide in Canvas.
Day 3
Day 4
Pen-and-paper midterm in class
Recommended Schedule
Day 1
- Treaps and Skip Lists
- Do this mixed review worksheet on self balancing trees. Then check this key.
Day 2
- Review for the midterm. See the study guide in Canvas.
Day 3
Day 4
Take midterm? If you are not taking the midterm until next week, make sure you use this time to finish up assignment 4 and consider working ahead on the rest of Ch 33.
Treaps and Skip Lists
There are some clever ways we can use randomness to help us maintain balance in a tree. They do not provide the same worst-case guarantees as AVL or Red-Black trees, but they are simpler to implement and we can still expect to get logn performance on average.
Watch this video:
Hashing
This material is NOT on the midterm. We will continue it next week.
Read Ch 33.1-33.5.
These videos review the material:
Concept of hashing: (Ch 33.1-33.2)
How to compute hashes for hash tables: (Ch 33.3-33.5)