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, 18:57):
Recap - Sorted Dictionary and BSTs
- Video 1-2 (2026-04-13, 7:20):
What’s wrong with BBSTs?
- Video 1-3 (2026-04-13, 24:50):
Random BST model
- Video 1-4 (2026-04-14, 1:14:41):
Properties of Random BSTs
- Video 1-5 (2026-04-20, 17:33):
Treaps
- Video 1-6 (2026-04-20, 44:12):
Updates in Treaps
- Video 1-7 (2026-04-20, 12:09):
Insert at root
- Video 1-8 (2026-04-21, 18:20):
Randomized BSTs
- Video 1-9 (2026-04-21, 38:36):
Skip lists
- Video 1-10 (2026-04-21, 7:29):
Skip list updates
- Video 1-11 (2026-04-27, 13:58):
Jumplists
- Video 1-12 (2026-04-27, 10:19):
Jumplists search analysis
- Video 1-13 (2026-04-27, 16:57):
Jumplists updates
- Video 1-14 (2026-04-27, 13:20):
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