數(shù)據(jù)結(jié)構(gòu) 課件 3-跳表

數(shù)據(jù)結(jié)構(gòu)計算機(jī)領(lǐng)域本科教育教學(xué)改革試點工作計劃（“101計劃”）研究成果10112.3跳表第12章

高級查找戴波電子科技大學(xué)12.3.1跳表的定義12.3.2跳表的查找12.3.3跳表的插入12.3.4跳表的刪除12.3.5跳表的復(fù)雜度分析12.3.6跳表的作業(yè)12.3.1跳表的定義12.3.1跳表的定義數(shù)據(jù)結(jié)構(gòu)跳表由若干層有序鏈表組成，其中第一層鏈表為原始的有序鏈表，之后每一層的鏈表僅保留前一層鏈表的部分結(jié)點，位于第i層的鏈表結(jié)點有超參數(shù)p（一般取0.5）的概率被保留在第i+1層中。如果繼續(xù)分層不再有任何結(jié)點被保留，則不再繼續(xù)分層，以當(dāng)前層作為跳表的最高層，記為第L層。下圖給出了一個跳表的例子，共有四層，L=4。每一層的有序鏈表結(jié)點除了存儲其在當(dāng)前層有序鏈表上的后繼結(jié)點指針（下圖中的向右指針）外，還存儲其對應(yīng)的前一層的有序鏈表中的結(jié)點指針（下圖中的向下指針）。12.3.1跳表的定義12.3.1跳表的定義數(shù)據(jù)結(jié)構(gòu)跳表在有序鏈表的基礎(chǔ)上引入“分層”的思想，使得查找、插入和刪除操作的時間復(fù)雜度能降至O(logn)。這里“分層”的思想與2.4.6中的塊狀鏈表“分塊”思想有一定的相似性，不過塊狀鏈表僅將鏈表分成了兩層，而跳表將鏈表分成了若干層。采用跳表，就是鏈表分層，查找，插入，刪除性能是O(logn)。12.3.2跳表的查找12.3.2跳表的查找數(shù)據(jù)結(jié)構(gòu)在跳表上需要查找值為k的元素時，首先從第L層開始從左往右找到當(dāng)前層最后一個值小于等于k的結(jié)點v。如果結(jié)點v存在，則跳轉(zhuǎn)至第L-1層與結(jié)點v對應(yīng)的結(jié)點，如果結(jié)點v不存在則跳轉(zhuǎn)至第L-1層的頭結(jié)點。隨后，在第L-1層繼續(xù)重復(fù)上述操作，在L-2層繼續(xù)重復(fù)上述操作……直至到達(dá)第一層。如果在第一層找到的結(jié)點v的值等于k，則返回查找結(jié)果，否則值為k的元素不存在，查找失敗。例：分別查找關(guān)鍵字17，5，2512.3.3跳表的插入12.3.3跳表的插入數(shù)據(jù)結(jié)構(gòu)向跳表中插入一個值為k的元素時，需要先執(zhí)行一遍查找操作，確定每一層有序鏈表中插入k的位置。隨后從第一層開始，將值為k的結(jié)點插入當(dāng)前層有序鏈表，然后以p的概率進(jìn)行一次隨機(jī)，決定是否要進(jìn)入上一層。如果要進(jìn)入上一層，則繼續(xù)在第二層重復(fù)上述操作，否則停止。需要注意的是，在插入元素時，有可能使跳表的總層數(shù)增加。例：假設(shè)P=0.6;插入18，進(jìn)入上面3層的概率分別是0.85,0.66,0.5012.3.4跳表的刪除12.3.4跳表的刪除數(shù)據(jù)結(jié)構(gòu)從跳表中刪除一個值為k的元素時，同樣需要先執(zhí)行一遍查找操作，隨后將查找路徑上值等于k的所有結(jié)點從所在層的有序鏈表中刪除。需要注意的是，刪除元素可能導(dǎo)致跳表總層數(shù)的減少。例：分別刪除19，7，2612.3.5跳表的復(fù)雜度分析12.3.4跳表的復(fù)雜度分析數(shù)據(jù)結(jié)構(gòu)

12.3.6作業(yè)12.3.6作業(yè)數(shù)據(jù)結(jié)構(gòu)分別輸出在下圖的跳表中查找關(guān)鍵字18和7的結(jié)點經(jīng)過的關(guān)鍵字序列。在下圖的跳表中，依次插入關(guān)鍵字22，8；再刪除關(guān)鍵字9和6，請繪制完成上述操作后的跳表。說明：關(guān)鍵字22進(jìn)入上一層的概率分別是0.8，0.2，0.6;關(guān)鍵