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

Class Schedule

Monday

  • Treaps and Skip Lists

Tuesday

  • Midterm Review

Wednesday

  • Hashing Intro

Thursday

Midterm

Topics

Probabilistically balanced structures - Treaps and Skip Lists

  • Watch this video:

Review

Study guide available in Class Files link

Hashing

  • Read Ch 24.1-24.3

  • Watch these videos: