Advanced Data Structures (Fall 2016)

Shay Mozes

Lecture 5 Video     [previous] [next]

[+] Predecessor/Successor search. Move-to-Front

We present two data structures for maintaining a dynamic set of integers under predecessor and successor queries - van Emde Boas trees, and y-fast tries. Towards the end of the lecture we begin a discussion of self balancing linked lists and competitive analysis.

Download Video: 720p

[No lecture notes for this lecture.]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email me.