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

Class Schedule

Monday

  • Treaps and Skip Lists

Tuesday

  • Midterm Review

Wednesday

  • Hashing Intro

Thursday

Pen-and-paper midterm in class

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