淺談“跳躍表”的相關(guān)操作及其應用

1、讓算法的效率“跳起來”！ 淺談“跳躍表”的相關(guān)操作及其應用 “跳躍表” 新生的寵兒 跳躍表（skip list）是1987年才誕生的一種嶄新的數(shù)據(jù)結(jié)構(gòu)，它在進行查找、插入、刪除等操作時的時間復雜度均為o(logn),有著近乎替代平衡樹的本領(lǐng)。而且最重要的一點，就是它的編程復雜度較同類的avl樹，紅黑樹等要低得多，這使得其無論是在理解還是在推廣性上，都有著十分明顯的優(yōu)勢?！疤S表”的結(jié)構(gòu)跳躍表由多條鏈構(gòu)成（s0，s1，s2 ，sh），且滿足如下三個條件：1.每條鏈必須包含兩個特殊元素：+ 和 -2.s0包含所有的元素，并且所有鏈中的元素按照升序排列。3.每條鏈中的元素集合必須包含于序數(shù)較小的鏈的

2、元素集合，即：hssss.210hssss.210hssss.21053 53 53 45 45 37 30 30 30 29 15 11 11 11 11 - - - - + + + + s0 s1 s2 s3 跳躍表的實例“跳躍表” 的時空效率 空間復雜度： o(n) （期望） 跳躍表高度： o(logn)（期望）相關(guān)操作的時間復雜度：查找： o(logn)（期望）插入： o(logn)（期望）刪除： o(logn)（期望）基本操作一 查找目的：在跳躍表中查找一個元素 x在跳躍表中查找一個元素x，按照如下幾個步驟進行：i.從最上層的鏈（sh）的開頭開始ii.假設(shè)當前位置為p，它向右指向的節(jié)

3、點為q（p與q不一定相鄰），且q的值為y。將y與x作比較lx=y輸出查詢成功，輸出相關(guān)信息lxy從p向右移動到q的位置lxy從p向下移動一格iii.如果當前位置在最底層的鏈中（s0），且還要往下移動的話，則輸出查詢失敗53 53 53 45 45 37 30 30 30 29 15 11 11 11 11 - - - - + + + + 查詢元素53的全過程s0 s1 s2 s3 查找成功！基本操作二 插入目的：在跳躍表中插入一個元素 x 插入操作由兩部分組成：查找插入的位置和插入對應元素。為了確定插入的“列高”，我們引入一個隨機決策模塊：產(chǎn)生一個0到1的隨機數(shù)rr random()如果r小于

4、一個概率因子p，則執(zhí)行方案a，if rpthen do a否則，執(zhí)行方案belse do b列的初始高度為1。插入元素時，不停地執(zhí)行隨機決策模塊。如果要求執(zhí)行的是a操作，則將列的高度加1，并且繼續(xù)反復執(zhí)行隨機決策模塊。直到第i次，模塊要求執(zhí)行的是b操作，我們結(jié)束決策，并向跳躍表中插入一個高度為i的列。基本操作二 插入 假設(shè)我們現(xiàn)在要插入一個元素40到已有的跳躍表中。37 30 30 30 29 15 - - - - s0 s1 s2 s3 插入的位置53 53 53 45 45 + + + + 40 40 4040 高度+1隨機化模塊運行狀況：高度=4高度+1高度+1 結(jié)束53 - - - -

5、 s0 s1 s2 s3 基本操作三 刪除目的：從跳躍表中刪除一個元素 x刪除操作分為以下三個步驟：1.在跳躍表中查找到這個元素的位置，如果未找到，則退出2.將該元素所在整列從表中刪除3.將多余的“空鏈”刪除11 11 11 11 53 53 53 45 45 37 30 30 30 29 15 + + + + 53 53 53 45 45 37 30 30 30 29 15 - - - + + + s0 s1 s2 概率因子 p 對跳躍表的影響在插入操作中，我們引入了一個概率因子p，它決定了跳躍表的高度，并影響到了整個數(shù)據(jù)結(jié)構(gòu)的效率。讓我們來看看在實際評測過程中，不同的p在時空效率上的差異。

6、p 平均操作時間 平均列高 總結(jié)點數(shù) 每次查找跳躍次數(shù)（平均值） 每次插入跳躍次數(shù)（平均值） 每次刪除跳躍次數(shù)（平均值） 2/3 0.0024690 ms 3.004 91233 39.87841.60441.5661/2 0.0020180 ms1.995 60683 27.80729.94729.0721/e 0.0019870 ms1.584 47570 27.33228.23828.4521/4 0.0021720 ms1.33040478 28.72629.47229.6641/8 0.0026880 ms1.14434420 35.14735.82136.007跳躍表的應用 高效率

7、的相關(guān)操作和較低的編程復雜度使得跳躍表在實際應用中的范圍十分廣泛。尤其在那些編程時間特別緊張的情況下，高性價比的跳躍表很可能會成為你的得力助手。您正為找不到合適的數(shù)據(jù)結(jié)構(gòu)而感到煩惱嗎？您正為自己編寫程序的效率高低而感到擔憂嗎？您正為陷入r-b tree的深淵又無法自拔而感到苦悶嗎？朋友！試試跳躍表吧！它將給您的編程帶來超高的效率與無盡的快樂！機不可失，時不再來！詳情請致電：1381xxxxxxx跳躍表的應用 noi2004 day1 郁悶的出納員（cashier） 抽象題意：要求維護這樣一個數(shù)據(jù)結(jié)構(gòu)，使得它支持以下四種操作：i(x)插入一個值為 x 元素a(x)現(xiàn)有全體元素加上一個值 xs(x

8、)現(xiàn)有全體元素減去一個值 xf(i)查找現(xiàn)有元素中第 i 大的元素值（x為105級別）同時還要保持這樣一個性質(zhì)：現(xiàn)有的元素必須都大于一個特定的值min，小于min的要刪去。 我們利用一個虛擬的“零線”來表示0在數(shù)據(jù)結(jié)構(gòu)中的相對位置。這樣在進行a和s操作的時候，只要對“零線”進行調(diào)整即可，并不需要對所有元素的值做全面的修改。而在做s操作時，為了維持題意中的性質(zhì)，要注意將值低于（“零線”+min）的元素刪除。 支持這些操作的數(shù)據(jù)結(jié)構(gòu)有很多，比如說線段樹，伸展樹，跳躍表等。跳躍表的應用 noi2004 day1 郁悶的出納員（cashier）評測結(jié)果：（單位：秒）test1test2test3tes

9、t4test5test6test7test8test9test10線段樹0.0000.0000.0000.0310.0620.0940.1090.2030.2650.250伸展樹0.0000.0000.0160.0620.0470.1250.1410.3600.4530.422跳躍表0.0000.0000.0000.0470.0620.1090.1560.3680.4380.375i命令時間復雜度 a命令時間復雜度 s命令時間復雜度 f命令時間復雜度 線段樹o(logr) o(1) o(logr) o(logr) 伸展樹 o(logn) o(1) o(logn) o(logn) 跳躍表 o(logn) o(1) o(logn) o(logn) 1. 空間復雜度o（n）2. 擺脫實數(shù)的約束3. 極小的編程復雜度能夠使你很短的內(nèi)解決此題！跳躍表的應用 hnoi2004 day1 寵物收養(yǎng)所 （pet） 抽象題意：維護一個數(shù)據(jù)結(jié)構(gòu)，使得它支持以下兩種操作： 插入一個元素 x (0 x231) 給定一個元素y，刪除現(xiàn)有與y差值最小的元素x （|x-y|為最?。┧胁僮鞔螖?shù)不超過80000思考.線段樹? 如果采取邊做邊開空間的策略，勉強可以緩解內(nèi)存的壓力。但此題對內(nèi)存的要求很苛刻，元素相對范圍來說也比較少，如果插入的元素稍微分散一些，就很有可能使得空間復雜度