Lecture 12: Skip Lists

author: Erik Demaine, Center for Future Civic Media
recorded by: Massachusetts Institute of Technology, MIT
published: Feb. 10, 2009,   recorded: October 2005,   views: 7294
released under terms of: Creative Commons Attribution No Derivatives (CC-BY-ND)

Slides

Related content

Report a problem or upload files

If 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.
Lecture popularity: You need to login to cast your vote.
  Delicious Bibliography

Description

"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..."

See Also:

Download slides icon Download slides: mit6046jf05_demaine_lec12_01.pdf (300.4 KB)

Download Video - generic video source Download mit6046jf05_demaine_lec12_01.m4v (Video - generic video source 179.2 MB)

Download Video - generic video source Download mit6046jf05_demaine_lec12_01.rm (Video - generic video source 136.8 MB)

Download Video Download mit6046jf05_demaine_lec12_01.flv (Video 236.3 MB)

Download Video Download mit6046jf05_demaine_lec12_01.wmv (Video 755.6 MB)

Download audio transcript Download mit6046jf05_demaine_lec12_01.mp3 (Audio lecture 19.7 MB)


Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 algirduxx, November 27, 2010 at 2:45 p.m.:

Thank You, Sir, for great Skip List lecture.
That's a great teacher!


Comment2 sean kaday , January 21, 2012 at 8:13 a.m.:

serch is stupid skroul enjin list all
list all
liat all
list all
list all
list all
list all
list all black out all masterd knolige


Comment3 sean kaday , January 21, 2012 at 8:32 a.m.:

serch is stupid skroul enjin list all
list all
liat all
list all
list all
list all
list all
list all black out all masterd knolige sapose you you start out knowing nuthing now serch linerer mastery press play

the hieraky of relivince

exampel jupoter 1 planit 2 size 3 distince from the sun 4 year 5 day
link merkuey venou earth mars j satern youanis neptoun ploto


Comment4 sean kaday , January 21, 2012 at 8:45 a.m.:

serch is stupid skroul enjin list all
list all
liat all
list all
list all
list all
list all
list all black out all masterd knolige sapose you you start out knowing nuthing now serch linerer mastery press play

the hieraky of relivince

exampel jupoter 1 planit 2 size 3 distince from the sun 4 year 5 day
link merkuey venou earth mars j satern youanis neptoun ploto

tree link wood all wood
all trees
bitanikals
all bitanikals
living things
all living things presint
all living things extent

brid all brids
animal all animals
living things

car all cars
moterveikal all moterviikal
moad of tranpertashon
all presint all past
hourse
animal

elimint all elimints
molikul all molikela
chemikal
all chenikals
loqwid all poyiling point
solids all melting toint kwontity
gasses all

all kolige is stord hear press play


Comment5 sean kaday , January 21, 2012 at 8:50 a.m.:

serch is stupid skroul enjin list all
list all
liat all
list all
list all
list all
list all
list all black out all masterd knolige sapose you you start out knowing nuthing now serch linerer mastery press play

the hieraky of relivince

exampel jupoter 1 planit 2 size 3 distince from the sun 4 year 5 day
link merkuey venou earth mars j satern youanis neptoun ploto

tree link wood all wood
all trees
bitanikals
all bitanikals
living things
all living things presint
all living things extent

brid all brids
animal all animals
living things

car all cars
moterveikal all moterviikal
moad of tranpertashon
all presint all past
hourse
animal

elimint all elimints
molikul all molikela
chemikal
all chenikals
loqwid all poyiling point
solids all melting toint kwontity
gasses all

all kolige is stord hear press play

prevew black out all known information

exampil run the definishon is 13.5 minouts long

ejukshon is entrtanment press play


Comment6 sean kaday , January 21, 2012 at 8:53 a.m.:

serch is stupid skroul enjin list all
list all
liat all
list all
list all
list all
list all
list all black out all masterd knolige sapose you you start out knowing nuthing now serch linerer mastery press play

the hieraky of relivince

exampel jupoter 1 planit 2 size 3 distince from the sun 4 year 5 day
link merkuey venou earth mars j satern youanis neptoun ploto

tree link wood all wood
all trees
bitanikals
all bitanikals
living things
all living things presint
all living things extent

brid all brids
animal all animals
living things

car all cars
moterveikal all moterviikal
moad of tranpertashon
all presint all past
hourse
animal

elimint all elimints
molikul all molikela
chemikal
all chenikals
loqwid all poyiling point
solids all melting toint kwontity
gasses all

all kolige is stord hear press play

prevew black out all known information

exampil run the definishon is 13.5 minouts long

ejukshon is entrtanment press play

eliminat the profit motive universel picher lagwige diferencheashon is kowing the diferince between simmilaritys and casimis kontrasts


Comment7 sean kaday , January 21, 2012 at 8:54 a.m.:

serch is stupid skroul enjin list all
list all
liat all
list all
list all
list all
list all
list all black out all masterd knolige sapose you you start out knowing nuthing now serch linerer mastery press play

the hieraky of relivince

exampel jupoter 1 planit 2 size 3 distince from the sun 4 year 5 day
link merkuey venou earth mars j satern youanis neptoun ploto

tree link wood all wood
all trees
bitanikals
all bitanikals
living things
all living things presint
all living things extent

brid all brids
animal all animals
living things

car all cars
moterveikal all moterviikal
moad of tranpertashon
all presint all past
hourse
animal

elimint all elimints
molikul all molikela
chemikal
all chenikals
loqwid all poyiling point
solids all melting toint kwontity
gasses all

all kolige is stord hear press play

prevew black out all known information

exampil run the definishon is 13.5 minouts long

ejukshon is entrtanment press play

eliminat the profit motive universel picher lagwige diferencheashon is kowing the diferince between simmilaritys and casimis kontrasts

syixtey simbels
why stop their


Comment8 sean kaday , January 21, 2012 at 8:56 a.m.:

serch is stupid skroul enjin list all
list all
liat all
list all
list all
list all
list all
list all black out all masterd knolige sapose you you start out knowing nuthing now serch linerer mastery press play

the hieraky of relivince

exampel jupoter 1 planit 2 size 3 distince from the sun 4 year 5 day
link merkuey venou earth mars j satern youanis neptoun ploto

tree link wood all wood
all trees
bitanikals
all bitanikals
living things
all living things presint
all living things extent

brid all brids
animal all animals
living things

car all cars
moterveikal all moterviikal
moad of tranpertashon
all presint all past
hourse
animal

elimint all elimints
molikul all molikela
chemikal
all chenikals
loqwid all poyiling point
solids all melting toint kwontity
gasses all

all kolige is stord hear press play

prevew black out all known information

exampil run the definishon is 13.5 minouts long

ejukshon is entrtanment press play

eliminat the profit motive universel picher lagwige diferencheashon is kowing the diferince between simmilaritys and casimis kontrasts

syixtey simbels
why stop their

the cad internet 3d left right up down in out


Comment9 sean kaday , January 21, 2012 at 9:02 a.m.:

serch is stupid skroul enjin list all
list all
liat all
list all
list all
list all
list all
list all black out all masterd knolige sapose you you start out knowing nuthing now serch linerer mastery press play

the hieraky of relivince

exampel jupoter 1 planit 2 size 3 distince from the sun 4 year 5 day
link merkuey venou earth mars j satern youanis neptoun ploto

tree link wood all wood
all trees
bitanikals
all bitanikals
living things
all living things presint
all living things extent

brid all brids
animal all animals
living things

car all cars
moterveikal all moterviikal
moad of tranpertashon
all presint all past
hourse
animal

elimint all elimints
molikul all molikela
chemikal
all chenikals
loqwid all poyiling point
solids all melting toint kwontity
gasses all

all kolige is stord hear press play

prevew black out all known information

exampil run the definishon is 13.5 minouts long

ejukshon is entrtanment press play

eliminat the profit motive universel picher lagwige diferencheashon is kowing the diferince between simmilaritys and casimis kontrasts

syixtey simbels
why stop their

the cad internet 3d left right up down in out

know mater how mutch infomation your our sistem pozesis that info is finite
so siplify
1 sparo
1 hock
1 finit and universel
kolige is not infinit you are only as good as your freeist sistem


Comment10 sean kaday , January 21, 2012 at 9:06 a.m.:

serch is stupid skroul enjin list all
list all
liat all
list all
list all
list all
list all
list all black out all masterd knolige sapose you you start out knowing nuthing now serch linerer mastery press play

the hieraky of relivince

exampel jupoter 1 planit 2 size 3 distince from the sun 4 year 5 day
link merkuey venou earth mars j satern youanis neptoun ploto

tree link wood all wood
all trees
bitanikals
all bitanikals
living things
all living things presint
all living things extent

brid all brids
animal all animals
living things

car all cars
moterveikal all moterviikal
moad of tranpertashon
all presint all past
hourse
animal

elimint all elimints
molikul all molikela
chemikal
all chenikals
loqwid all poyiling point
solids all melting toint kwontity
gasses all

all kolige is stord hear press play

prevew black out all known information

exampil run the definishon is 13.5 minouts long

ejukshon is entrtanment press play

eliminat the profit motive universel picher lagwige diferencheashon is kowing the diferince between simmilaritys and casimis kontrasts

syixtey simbels
why stop their

the cad internet 3d left right up down in out

know mater how mutch infomation your our sistem pozesis that info is finite
so siplify
1 sparo
1 hock
1 finit and universel
kolige is not infinit you are only as good as your freeist sistem
sertch is stupid
if the limit of your knolidge is what you their is no posibility to expand

Write your own review or comment:

make sure you have javascript enabled or clear this field: