Week 8 - Balanced Trees

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
Your midterm must be taken this week. Make sure it is scheduled! See the discussion board.

Day 1

Probabilistically balanced structures - Treaps and Skip Lists

  • There are some clever ways we can use randomness to be pretty sure that we will get logn performance from a structure that provides similar functionality to a BST without keeping track of heights or colors. Watch this video:

Day 2

Review

Midterm study guide available in Class Files link

Day 3

Midterm

Take midterm

Day 4

Hashing

  • Hashing is an important general concept in CS. It is the idea of transforming a large chunk of information into a fixed-sized, smaller string. Hashing is used in various cryptography and security-related algorithms and to build data structures. Watch these videos for more information:

  • Read Ch 24.1-24.3