這篇文章主要講解了“數(shù)據(jù)結(jié)構(gòu)與算法之如何掌握跳表”，文中的講解內(nèi)容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“數(shù)據(jù)結(jié)構(gòu)與算法之如何掌握跳表”吧！

創(chuàng)新互聯(lián)建站2013年開創(chuàng)至今，先為下城等服務(wù)建站，下城等地企業(yè)，進行企業(yè)商務(wù)咨詢服務(wù)。為下城企業(yè)網(wǎng)站制作PC+手機+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。

數(shù)據(jù)結(jié)構(gòu)與算法筆記-數(shù)據(jù)結(jié)構(gòu)-跳表

跳表(skip list)

跳表代碼-gitee

跳表代碼-github

關(guān)鍵詞

1. 跳表是基于鏈表的一種動態(tài)數(shù)據(jù)結(jié)構(gòu),可以簡單認為就是對鏈表的節(jié)點添加了多級索引.

2. 跳表支持快速地插入,刪除,查找操作,時間復雜度都是O(logn),空間復雜度為O(n)

3. 跳表是通過添加索引使用空間換時間的設(shè)計思路,構(gòu)建多級索引來提升查詢效率

4. 跳表的時間復雜度為O(logn)

5. 跳表數(shù)通過隨機函數(shù)來維護平衡

6. 跳表插入數(shù)據(jù)時要維護索引和節(jié)點的平衡,否則極端情況下可能會導致跳表退化成為鏈表

7. 跳表更加靈活,可以通過改變索引構(gòu)建策略,有效平衡執(zhí)行效率和內(nèi)存消耗.

8. 跳表有可與紅黑樹匹敵的性能,跳表寫起來卻好寫很多.很多時候可以直接替代紅黑樹

9. 按照區(qū)間來查找數(shù)據(jù)這個操作,紅黑樹的效率沒有跳表高.對于按照區(qū)間查找數(shù)據(jù)這個操作,跳表可以做到,O(logn) 的時間復雜度定位區(qū)間的起點,而后在原始鏈表中順序往后遍歷即可

理解跳表

二分查找法底層依賴的時數(shù)組隨機訪問的特性,所以只能用數(shù)組來實現(xiàn).

鏈表也有類似二分的查找操作, 叫做跳表(skip list)

鏈表是一種各方面性能都很優(yōu)秀的動態(tài)數(shù)據(jù)結(jié)構(gòu),支持: 快速插入,刪除,查找.寫起來也簡單, 甚至可以代替紅黑樹.

其中redis的有序列表(sorted set)就是利用跳表來實現(xiàn)的,因為:

嚴格來說Redis還用到了Hash table
主要Redis手冊,有序集合的核心操作就是
	插入一個數(shù)據(jù)；
	刪除一個數(shù)據(jù)；
	查找一個數(shù)據(jù)；
	按照區(qū)間查找數(shù)據(jù)（比如查找值在[100, 356]之間的數(shù)據(jù)）；
	迭代輸出有序序列。
	
其中，插入、刪除、查找以及迭代輸出有序序列這幾個操作，紅黑樹也可以完成，時間復雜度跟跳表是一樣的。但是，按照區(qū)間來查找數(shù)據(jù)這個操作，紅黑樹的效率沒有跳表高。
對于按照區(qū)間查找數(shù)據(jù)這個操作，跳表可以做到 O(logn) 的時間復雜度定位區(qū)間的起點，然后在原始鏈表中順序往后遍歷就可以了
還有，跳表更加靈活，它可以通過改變索引構(gòu)建策略，有效平衡執(zhí)行效率和內(nèi)存消耗。

單項鏈表的數(shù)據(jù)就算是有序的,要獲取指定的數(shù)據(jù)也要從頭逐個遍歷,時間復雜度為O(n)

如圖:

一級索引

想要提高查詢效率,可以通過對鏈表建一級索引來實現(xiàn).在每兩個節(jié)點中提取一個節(jié)點到作為索引或索引層

如圖: 下面的down代表下一個節(jié)點的指針

設(shè)若獲取節(jié)點16:

1. 先遍歷索引層,當遍歷到索引層中值為13的節(jié)點時,發(fā)現(xiàn)下一個節(jié)點是17,那節(jié)點16必然就在這兩個節(jié)點之間.

2. 通過索引層及誒單的down指針,到原始接鏈表中繼續(xù)向后遍歷

3. 此時,只需再向后遍歷兩個及誒單即可找到值等于16的節(jié)點

4. 原來需要查找16次,現(xiàn)在只要7次遍歷

可見, 加一層索引之后,查找一個節(jié)點需要遍歷的次數(shù)就減少了很多,查找效率提升很高.

二級索引

和建立第一級索引的方式類似, 在第一級索引的基礎(chǔ)上,每兩個節(jié)點抽出一個節(jié)點到第二級作為二級索引.

此時再來查找16,只需要遍歷6個節(jié)點.

如圖:

當數(shù)據(jù)量夠大,夠大的時候, 查詢效率會有更大的提升,下圖一個64個節(jié)點的鏈表.建立了五級索引

要找到值為62的節(jié)點, 在沒有索引時需要遍歷62個節(jié)點.

現(xiàn)在只需要遍歷11個節(jié)點即可

如圖:

上面這種鏈表加多級索引的結(jié)構(gòu)就是跳表,可以看到跳表大大減少了查詢次數(shù).對鏈表的優(yōu)化是顯而易見的.

跳表查詢有多快

單項鏈表中查詢指定數(shù)據(jù)的時間復雜度是O(n)

具有多級索引的跳表中, 假設(shè)有n個節(jié)點需要多少級索引:

設(shè),若每兩個節(jié)點抽出一個節(jié)點作為上一級索引

1. 第一級索引約為n/2個

2. 第二級索引約為n/4個

3. 第三極索引約為n/8個

4. 第四級索引約為n/16個

5. ......以此類推

6. 第k級索引的節(jié)點個數(shù)是k-1級索引的節(jié)點個數(shù)的1/2

7. 第k級索引節(jié)點的個數(shù)就是n/(2^k)

設(shè),索引有h級,最高級的索引有2個節(jié)點,

1. 套用上面的公式得到n/(2^h)=2,求得h=log2n-1

2. 如果包含原始鏈表這一層,整個跳表的高度就是log2n

3. 在跳表查詢某個數(shù)據(jù)時,若每一次都要遍歷m個節(jié)點,那在跳表中查詢一個數(shù)據(jù)的時間復雜度就是O(m*logn)

多級索引

如果每三個或五個抽出一個作為索引,如圖有14個節(jié)點:

1. 第一級索引需要n/3個節(jié)點

2. 第二級索引需要n/9個節(jié)點

3. ......每向上一級,索引的個數(shù)都除以3

4. 假設(shè)做高級的索引個數(shù)為1, 把每級節(jié)點個數(shù)列出來,就是一個等比數(shù)列

通過等比數(shù)列求和公式, 總的索引結(jié)點大約就是 n/3+n/9+n/27+…+9+3+1=n/2

盡管空間復雜度還是 O(n),但比上面的每兩個結(jié)點抽一個結(jié)點的索引構(gòu)建方法,要減少了一半索引結(jié)點存儲空間.

一般在真正的開發(fā)中,不考慮索引占的空間,索引結(jié)點只需要存儲關(guān)鍵值和幾個指針,并不需要存儲對象.

高效的動態(tài)插入和刪除

插入和刪除實際上是需要兩步的:

1. 找到合適的節(jié)點

2. 插入或刪除

查找

跳表還支持動態(tài)插入,刪除,切插入和刪除的時間復雜度都是O(logn)

相比之下,單項鏈表的插入是O(1),但是這是在定好插入位置之后的時間復雜度.

但是為了保證鏈表數(shù)據(jù)的順序性, 在插入之前還需要找到插入位置,查找一通這就費了勁了.

單向鏈表, 需要遍歷每一個節(jié)點來找到插入的位置

插入操作

上面說過了, 跳表通過查找指定節(jié)點的時間復雜度是O(logn),找到插入位置也一樣, 插入過程如下圖:

刪除操作

1. 如果這個節(jié)點同時在索引中,想要刪除原始鏈表中的節(jié)點,同時還要刪除索引中的節(jié)點.

2. 單項連表的刪除操作需要拿到要該節(jié)點的前一個節(jié)點,然后通過指針來刪除后一個節(jié)點,以完成刪除該節(jié)點的操作.

3. 所以在查找要刪除的節(jié)點時,一定要獲取到該節(jié)點的前一個節(jié)點.(雙向鏈表不考慮這個問題)

跳表索引動態(tài)更新

在不斷的插入數(shù)據(jù)而不去更新索引時,可能會出現(xiàn)兩個索引之間節(jié)點數(shù)特別多的情況.

在極端情況下,會導致跳表退化成為鏈表.

如下圖:

跳表作為一個動態(tài)數(shù)據(jù)結(jié)構(gòu),需要我們不斷地維護索引與原始鏈表之間的平衡.

如果鏈表節(jié)點多了,索引節(jié)點就要增加,以避免復雜度退化,導致查找和刪除性能下降.

紅黑樹和avl數(shù)是通過左右旋的方式保持左右子樹的大小平衡,而跳表數(shù)通過隨機函數(shù)來維護平衡.

通過隨機函數(shù),決定該節(jié)點插入到哪幾級索引中,

如隨機函數(shù)生成了值k,那就將這個節(jié)點添加到第一級到第K級的, 這幾級的索引中

如下圖:

隨機函數(shù)要比較高,從概率上來講要保證跳表的索引大小和數(shù)據(jù)大小平衡性,不至于性能過度退化.

感謝各位的閱讀，以上就是“數(shù)據(jù)結(jié)構(gòu)與算法之如何掌握跳表”的內(nèi)容了，經(jīng)過本文的學習后，相信大家對數(shù)據(jù)結(jié)構(gòu)與算法之如何掌握跳表這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！

標題名稱：數(shù)據(jù)結(jié)構(gòu)與算法之如何掌握跳表
文章網(wǎng)址：http://jinyejixie.com/article38/gdpisp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、定制網(wǎng)站、網(wǎng)站建設(shè)、品牌網(wǎng)站制作、虛擬主機、動態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)