Unit 1: Randomized Trees

This unit covers:

• random BSTs
• treaps
• randomized BSTs
• skip lists
• jumplists

Material

• preliminary slides

• lecture notes

• Video 1-1 (2026-04-13): Recap - Sorted Dictionary and BSTs

• Video 1-2 (2026-04-13): What’s wrong with BBSTs?

• Video 1-3 (2026-04-13): Random BST model

• Video 1-4 (2026-04-14): Properties of Random BSTs

• Video 1-5 (2026-04-20): Treaps

• Video 1-6 (2026-04-20): Updates in Treaps

• Video 1-7 (2026-04-20): Insert at root

Further sources

Much of the presentation is my own, but similar material can be found in the following sources:

• Morin. Open Data Structures

---

Unit 0  ⋅  Syllabus  ⋅  Unit 2