[+] Move to front and self-adjusting binary search trees. |
| We analyze the Move-to-Front heuristic for self-adjusting linked lists and show that it is 2-competitive both in the static and in the dynamic settings. We then begin discussing binary search trees. We show an algorithm for constructing an optimal search tree in the stochastic settings and begin discussion of rotations towards describing splay trees. |
|
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.