第03章跳躍表SkipLists教案資料

SkipLists+

-

S0S1S2S3+

-

10362315+

-

15+

-

23159/27/20241SkipListsOutlineandReadingWhatisaskiplist(§3.5)OperationsSearch(§3.5.1)Insertion(§3.5.2)Deletion(§3.5.2)ImplementationAnalysis(§3.5.3)SpaceusageSearchandupdatetimesComparisonofdictionaryimplementations9/27/20242SkipListsWhatisaSkipListAskiplistforasetSofdistinct(key,element)itemsisaseriesoflistsS0,S1,…,ShsuchthatEachlistSicontainsthespecialkeys+

and-

ListS0containsthekeysofSinnondecreasingorderEachlistisasubsequenceofthepreviousone,i.e.,

S0

S1

…

ShListShcontainsonlythetwospecialkeysWeshowhowtouseaskiplisttoimplementthedictionaryADT566478+

313444-

122326+

-

+

31-

64+

3134-

23S0S1S2S39/27/20243SkipListsSearchWesearchforakeyxinaaskiplistasfollows:WestartatthefirstpositionofthetoplistAtthecurrentpositionp,wecomparexwithy

key(after(p)) x=y:wereturnelement(after(p)) x>y:we“scanforward” x<y:we“dropdown”Ifwetrytodropdownpastthebottomlist,wereturnNO_SUCH_KEYExample:searchfor78+

-

S0S1S2S3+

31-

64+

3134-

23566478+

313444-

1223269/27/20244SkipListsToinsertanitem(x,o)intoaskiplist,weusearandomizedalgorithm:Werepeatedlytossacoinuntilwegettails,andwedenotewithithenumberoftimesthecoincameupheadsIfi

h,weaddtotheskiplistnewlistsSh+1,…,Si+1,eachcontainingonlythetwospecialkeysWesearchforxintheskiplistandfindthepositionsp0,

p1,…,pioftheitemswithlargestkeylessthanxineachlistS0,S1,…,SiForj

0,…,i,weinsertitem(x,o)intolistSjafterpositionpjExample:insertkey15,withi

=2Insertion+

-

1036+

-

2323+

-

S0S1S2+

-

S0S1S2S3+

-

10362315+

-

15+

-

2315p0p1p29/27/20246SkipListsDeletionToremoveanitemwithkeyx

fromaskiplist,weproceedasfollows:Wesearchforxintheskiplistandfindthepositionsp0,

p1,…,pioftheitemswithkeyx,wherepositionpjisinlistSjWeremovepositionsp0,

p1,…,pifromthelistsS0,S1,…,SiWeremoveallbutonelistcontainingonlythetwospecialkeysExample:removekey34-

+

4512-

+

2323-

+

S0S1S2-

+

S0S1S2S3-

+

45122334-

+

34-

+

2334p0p1p29/27/20247SkipListsImplementationWecanimplementaskiplistwithquad-nodesAquad-nodestores:itemlinktothenodebeforelinktothenodeafterlinktothenodebelowlinktothenodeafterAlso,wedefinespecialkeysPLUS_INFandMINUS_INF,andwemodifythekeycomparatortohandlethemxquad-node9/27/20248SkipListsSpaceUsageThespaceusedbyaskiplistdependsontherandombitsusedbyeachinvocationoftheinsertionalgorithmWeusethefollowingtwobasicprobabilisticfacts:Fact1:Theprobabilityofgettingiconsecutiveheadswhenflippingacoinis1/2iFact2:Ifeachofnitemsispresentinasetwithprobabilityp,theexpectedsizeofthesetisnpConsideraskiplistwithnitemsByFact1,weinsertaniteminlistSiwithprobability1/2iByFact2,theexpectedsizeoflistSiisn/2i

TheexpectednumberofnodesusedbytheskiplistisThus,theexpectedspaceusageofaskiplistwithnitemsisO(n)9/27/20249SkipListsHeightTherunningtimeofthesearchaninsertionalgorithmsisaffectedbytheheighthoftheskiplistWeshowthatwithhighprobability,askiplistwithnitemshasheightO(logn)Weusethefollowingadditionalprobabilisticfact:Fact3:Ifeachofneventshasprobabilityp,theprobabilitythatatleastoneeventoccursisatmostnpConsideraskiplistwithnitemsByFact1,weinsertaniteminlistSiwithprobability1/2iByFact3,theprobabilitythatlistSihasatleastoneitemisatmostn/2iBypickingi

=3logn,wehavethattheprobabilitythatS3lognhasatleastoneitemis

atmost

n/23logn

=n/n3

=1/n2Thusaskiplistwithnitemshasheightatmost3lognwithprobabilityatleast1-1/n29/27/202410SkipListsSearchandUpdateTimesThesearchtimeinaskiplistisproportionaltothenumberofdrop-downsteps,plusthenumberofscan-forwardstepsThedrop-downstepsareboundedbytheheightoftheskiplistandthusareO(logn)withhighprobabilityToanalyzethescan-forwardsteps,weuseyetanotherprobabilisticfact:Fact4:Theexpectednumberofcointossesrequiredinordertogettailsis2Whenwescanforwardinalist,thedestinationkeydoesnotbelongtoahigherlistAscan-forwardstepisassociatedwithaformercointossthatgavetailsByFact4,ineachlisttheexpectednumberofscan-forwardstepsis2Thus,theexpectednumberofscan-forwardstepsisO(logn)WeconcludethatasearchinaskiplisttakesO(logn)expectedtimeTheanalysisofinsertionanddeletiongivessimilarresults9/27/202411SkipListsImplementingaDictionaryComparisonofefficientdictionaryimplementationsSearchInsertDeleteNotesHashTable1

expected1

expected1

expectednoordereddictionary

methodssimpletoimplementSkipListlogn

highprob.log