资源描述：
《lecture 12 skip lists》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、MITOpenCourseWarehttp://ocw.mit.edu6.046JIntroductiontoAlgorithms,Fall2005Pleaseusethefollowingcitationformat:ErikDemaineandCharlesLeiserson,6.046JIntroductiontoAlgorithms,Fall2005.(MassachusettsInstituteofTechnology:MITOpenCourseWare).http://ocw.mit.edu(accessedMMDD,YYYY).License:Creati
2、veCommonsAttribution-Noncommercial-ShareAlike.Note:Pleaseusetheactualdateyouaccessedthismaterialinyourcitation.FormoreinformationaboutcitingthesematerialsorourTermsofUse,visit:http://ocw.mit.edu/termsMITOpenCourseWarehttp://ocw.mit.edu6.046JIntroductiontoAlgorithms,Fall2005Transcript–Lec
3、ture12Goodmorning.Todaywe'regoingtotalkaboutitabalancedsearchstructure,soadatastructurethatmaintainsadynamicsetsubjecttoinsertion,deletion,andsearchcalledskiplists.So,I'llcallthisadynamicsearchstructurebecauseit'sadatastructure.Itsupportssearch,andit'sdynamic,meaninginsertanddelete.So,wh
4、atotherdynamicsearchstructuresdoweknow,justforsakeofcomparison,andtowakeeveryoneup?Shutthemout,efficient,Ishouldsay,alsogood,logarithmictimeperoperation.So,thisisareallyeasyquestiontogetusofftheground.You'veseenthemallinthelastweek,soitshouldn'tbesohard.Treap,good.Ontheproblemsthatwesawt
5、reaps.That's,insomesense,thesimplestdynamicsearchstructureyoucangetfromfirstprinciplesbecauseallweneededwasaboundonarandomlyconstructedbinarysearchtree.Andthentreapsdidwell.So,thatwassortofthefirstoneyousawdependingonwhenyoudidyourproblemset.Whatelse?Charles?Redblacktrees,goodanswer.So,t
6、hatwasexactlyoneweekago.Ihopeyoustillrememberit.Theyhaveguaranteedlognperformance.So,thiswasanexpectedbound.Thiswasaworst-caseorderlognperoperation,insert,delete,andsearch.And,therewasonemoreforthosewhowanttorecitationonFriday:Btrees,good.And,byBtrees,Ialsoincludetwo-threetrees,two-three
7、-fourtrees,andallthoseguys.So,ifBisaconstant,orifyouwantyourBtreesknowsalittlebitcleverly,thatthesehaveguaranteedorderlognperformance,so,worstcase,orderlogn.So,youshouldknowthis.Theseareallbalancedsearchstructures.Theyaredynamic.Theysupportinsertionsanddeletions.Theysuppo
