Advanced Data Structures (Fall 2016)

Shay Mozes

Lecture 8 Video     [previous] [next]

[+] Wilber's lower bound and Tango trees

We present a lower bound on self-adjusting binary search trees, and then show how Tango trees utilize this lower bound to be O(loglog n) competitive againt the dynamic optimium.

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.