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

  • Treaps and Skip Lists

Day 2

  • Midterm Review

Day 3

  • Hashing Intro

Day 4

  • Take Midterm

Topics

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:

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

Review

Midterm study guide available in Class Files link