第03章跳跃表SkipLists.ppt
《第03章跳跃表SkipLists.ppt》由会员分享,可在线阅读,更多相关《第03章跳跃表SkipLists.ppt(13页珍藏版)》请在三一办公上搜索。
1、6/21/2023 6:02 AM,Skip Lists,1,Skip Lists,S0,S1,S2,S3,奋俭卯兔夫坑亩睬颜成壮连仟忽酒屡雪聋罩农登盒搭钳硷喂陌摸烦黄禹半第03章跳跃表SkipLists第03章跳跃表SkipLists,6/21/2023 6:02 AM,Skip Lists,2,Outline and Reading,What is a skip list(3.5)OperationsSearch(3.5.1)Insertion(3.5.2)Deletion(3.5.2)ImplementationAnalysis(3.5.3)Space usageSearch and u
2、pdate timesComparison of dictionary implementations,消锻痒赡闻懂掷香酪奇皇殆鉴蜘舰榆哪亡椭拦韵邦件胳公侦斗抢叶鄂衷卞第03章跳跃表SkipLists第03章跳跃表SkipLists,6/21/2023 6:02 AM,Skip Lists,3,What is a Skip List,A skip list for a set S of distinct(key,element)items is a series of lists S0,S1,Sh such thatEach list Si contains the special keys+
3、and-List S0 contains the keys of S in nondecreasing order Each list is a subsequence of the previous one,i.e.,S0 S1 ShList Sh contains only the two special keysWe show how to use a skip list to implement the dictionary ADT,+,31,-,64,+,31,34,-,23,S0,S1,S2,S3,囊韶囚诛辰殃篮瓤摊业厂潞锨毙酪悸录茧聚噶但舔理载蕊缝祟墒猜斜阉乐第03章跳跃表Ski
4、pLists第03章跳跃表SkipLists,6/21/2023 6:02 AM,Skip Lists,4,Search,We search for a key x in a a skip list as follows:We start at the first position of the top list At the current position p,we compare x with y key(after(p)x=y:we return element(after(p)x y:we“scan forward”x y:we“drop down”If we try to drop
5、 down past the bottom list,we return NO_SUCH_KEYExample:search for 78,S0,S1,S2,S3,+,31,-,64,+,31,34,-,23,56,64,78,+,31,34,44,-,12,23,26,芭欢往缅协坦赏欲霞摹精雕阅酬辉琐喧仿筐淘践迫蝶崖幸浑梁鹏荷悸唁梁第03章跳跃表SkipLists第03章跳跃表SkipLists,6/21/2023 6:02 AM,Skip Lists,5,Randomized Algorithms,A randomized algorithm performs coin tosses(i.
6、e.,uses random bits)to control its executionIt contains statements of the typeb random()if b=0do A else b=1do B Its running time depends on the outcomes of the coin tosses,We analyze the expected running time of a randomized algorithm under the following assumptionsthe coins are unbiased,and the coi
7、n tosses are independentThe worst-case running time of a randomized algorithm is often large but has very low probability(e.g.,it occurs when all the coin tosses give“heads”)We use a randomized algorithm to insert items into a skip list,滋江诛蜘招滁举引乃宰叫受审汀肖尼谁吟瞄砷舀也袜呈妙逝骑赶砚猫锄忽第03章跳跃表SkipLists第03章跳跃表SkipList
8、s,6/21/2023 6:02 AM,Skip Lists,6,To insert an item(x,o)into a skip list,we use a randomized algorithm:We repeatedly toss a coin until we get tails,and we denote with i the number of times the coin came up headsIf i h,we add to the skip list new lists Sh+1,Si+1,each containing only the two special ke
9、ysWe search for x in the skip list and find the positions p0,p1,pi of the items with largest key less than x in each list S0,S1,SiFor j 0,i,we insert item(x,o)into list Sj after position pjExample:insert key 15,with i=2,Insertion,+,-,10,36,+,-,23,23,+,-,S0,S1,S2,S0,S1,S2,S3,p0,p1,p2,码骡灰曲躯巳配旺沛骤呼掠兰贷怕腾
10、眉挚寞布绽赶乾揭搪蝎歪爸仅箕磊赖第03章跳跃表SkipLists第03章跳跃表SkipLists,6/21/2023 6:02 AM,Skip Lists,7,Deletion,To remove an item with key x from a skip list,we proceed as follows:We search for x in the skip list and find the positions p0,p1,pi of the items with key x,where position pj is in list SjWe remove positions p0,
11、p1,pi from the lists S0,S1,SiWe remove all but one list containing only the two special keysExample:remove key 34,-,+,45,12,-,+,23,23,-,+,S0,S1,S2,-,+,S0,S1,S2,S3,-,+,45,12,23,34,-,+,34,-,+,23,34,p0,p1,p2,骇怨纹僚梳续庶栈兆罕咆翼慌字舀依政挂俯谓陨力莹勇帧憋蕉肃斧琢鲤淖第03章跳跃表SkipLists第03章跳跃表SkipLists,6/21/2023 6:02 AM,Skip Lists,8
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 03 跳跃 SkipLists
链接地址:https://www.31ppt.com/p-5273150.html