數據結構與算法之如何掌握跳表

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

數據結構與算法筆記-數據結構-跳表

跳表(skip list)

跳表代碼-gitee

跳表代碼-github

關鍵詞

1. 跳表是基于鏈表的一種動態數據結構,可以簡單認為就是對鏈表的節點添加了多級索引.

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

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

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

5. 跳表數通過隨機函數來維護平衡

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

7. 跳表更加靈活,可以通過改變索引構建策略,有效平衡執行效率和內存消耗.

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

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

理解跳表

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

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

鏈表是一種各方面性能都很優秀的動態數據結構,支持: 快速插入,刪除,查找.寫起來也簡單, 甚至可以代替紅黑樹.

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

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

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

如圖:

一級索引

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

如圖: 下面的down代表下一個節點的指針

設若獲取節點16:

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

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

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

4. 原來需要查找16次,現在只要7次遍歷

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

二級索引

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

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

如圖:

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

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

現在只需要遍歷11個節點即可

如圖:

上面這種鏈表加多級索引的結構就是跳表 ,可以看到跳表大大減少了查詢次數.對鏈表的優化是顯而易見的.

跳表查詢有多快

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

具有多級索引的跳表中, 假設有n個節點需要多少級索引:

設,若每兩個節點抽出一個節點作為上一級索引

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

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

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

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

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

6. 第k級索引的節點個數是k-1級索引的節點個數的1/2

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

設,索引有h級,最高級的索引有2個節點,

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

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

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

多級索引

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

1. 第一級索引需要n/3個節點

2. 第二級索引需要n/9個節點

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

4. 假設做高級的索引個數為1, 把每級節點個數列出來,就是一個等比數列

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

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

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

高效的動態插入和刪除

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

1. 找到合適的節點

2. 插入或刪除

查找

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

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

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

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

插入操作

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

刪除操作

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

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

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

跳表索引動態更新

在不斷的插入數據而不去更新索引時,可能會出現兩個索引之間節點數特別多的情況.

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

如下圖:

跳表作為一個動態數據結構,需要我們不斷地維護索引與原始鏈表之間的平衡.

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

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

通過隨機函數,決定該節點插入到哪幾級索引中,

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

如下圖:

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

感謝各位的閱讀，以上就是“數據結構與算法之如何掌握跳表”的內容了，經過本文的學習后，相信大家對數據結構與算法之如何掌握跳表這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！