Lecture 12: Skip Lists
recorded by: Massachusetts Institute of Technology, MIT
published: Feb. 10, 2009, recorded: October 2005, views: 8100
released under terms of: Creative Commons Attribution Non-Commercial Share Alike (CC-BY-NC-SA)
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
"Good morning. Today we're going to talk about it a balanced search structure, so a data structure that maintains a dynamic set subject to insertion, deletion, and search called skip lists. So, I'll call this a dynamic search structure because it's a data structure. It supports search, and it's dynamic, meaning insert and delete. So, what other dynamic search structures do we know, just for sake of comparison, and to wake everyone up? Shut them out, efficient, I should say, also good, logarithmic time per operation. So, this is a really easy question to get us off the ground..."
Download slides: mit6046jf05_demaine_lec12_01.pdf (300.4 KB)
Download mit6046jf05_demaine_lec12_01.m4v (Video - generic video source 179.2 MB)
Download mit6046jf05_demaine_lec12_01.rm (Video - generic video source 136.8 MB)
Download mit6046jf05_demaine_lec12_01.flv (Video 236.3 MB)
Download mit6046jf05_demaine_lec12_01.wmv (Video 755.6 MB)
Download mit6046jf05_demaine_lec12_01.mp3 (Audio lecture 19.7 MB)
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !