main page — CS 650 Advanced Data Structures
Unit 1: Randomized Trees
This unit covers:
- random BSTs
- treaps
- randomized BSTs
- skip lists
- jumplists
Material
- slides
- 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
- Video 1-8 (2026-04-21):
Randomized BSTs
- Video 1-9 (2026-04-21):
Skip lists
- Video 1-10 (2026-04-21):
Skip list updates
- Video 1-11 (2026-04-27):
Jumplists
- Video 1-12 (2026-04-27):
Jumplists search analysis
- Video 1-13 (2026-04-27):
Jumplists updates
- Video 1-14 (2026-04-27):
Fringe balancing
Further sources
Much of the presentation is my own, but similar material can be found in the following sources:
Jumplists follow our presentation in