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

• Review

Wednesday

Thursday

• Hashing Intro

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: