當(dāng)前位置：首頁 > 人文社科 > 生活经验 >内容正文

生活经验

skiplist 跳表（1）

發(fā)布時(shí)間：2023/11/27 生活经验 34 豆豆

生活随笔收集整理的這篇文章主要介紹了 skiplist 跳表（1）小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

最近學(xué)習(xí)中遇到一種新的數(shù)據(jù)結(jié)構(gòu)，很實(shí)用，搬過來學(xué)習(xí)。

原文地址：skiplist 跳表??

為什么選擇跳表

目前經(jīng)常使用的平衡數(shù)據(jù)結(jié)構(gòu)有：B樹，紅黑樹，AVL樹，Splay Tree, Treep等。

想象一下，給你一張草稿紙，一只筆，一個(gè)編輯器，你能立即實(shí)現(xiàn)一顆紅黑樹，或者AVL樹

出來嗎？很難吧，這需要時(shí)間，要考慮很多細(xì)節(jié)，要參考一堆算法與數(shù)據(jù)結(jié)構(gòu)之類的樹，

還要參考網(wǎng)上的代碼，相當(dāng)麻煩。

用跳表吧，跳表是一種隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)，目前開源軟件 Redis 和 LevelDB 都有用到它，

它的效率和紅黑樹以及 AVL 樹不相上下，但跳表的原理相當(dāng)簡單，只要你能熟練操作鏈表，

就能輕松實(shí)現(xiàn)一個(gè) SkipList。

有序表的搜索

考慮一個(gè)有序表：

從該有序表中搜索元素 < 23, 43, 59 > ，需要比較的次數(shù)分別為 < 2, 4, 6 >，總共比較的次數(shù)

為 2 + 4 + 6 = 12 次。有沒有優(yōu)化的算法嗎? ?鏈表是有序的，但不能使用二分查找。類似二叉

搜索樹，我們把一些節(jié)點(diǎn)提取出來，作為索引。得到如下結(jié)構(gòu)：

?這里我們把 < 14, 34, 50, 72 > 提取出來作為一級(jí)索引，這樣搜索的時(shí)候就可以減少比較次數(shù)了。

?我們還可以再從一級(jí)索引提取一些元素出來，作為二級(jí)索引，變成如下結(jié)構(gòu)：

? ? ?這里元素不多，體現(xiàn)不出優(yōu)勢(shì)，如果元素足夠多，這種索引結(jié)構(gòu)就能體現(xiàn)出優(yōu)勢(shì)來了。

跳表

下面的結(jié)構(gòu)是就是跳表：

?其中 -1 表示 INT_MIN，鏈表的最小值，1 表示 INT_MAX，鏈表的最大值。

跳表具有如下性質(zhì)：

(1) 由很多層結(jié)構(gòu)組成

(2) 每一層都是一個(gè)有序的鏈表

(3) 最底層(Level 1)的鏈表包含所有元素

(4) 如果一個(gè)元素出現(xiàn)在 Level i 的鏈表中，則它在 Level i 之下的鏈表也都會(huì)出現(xiàn)。

(5) 每個(gè)節(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指向同一鏈表中的下一個(gè)元素，一個(gè)指向下面一層的元素。

跳表的搜索

例子：查找元素 117

(1) 比較 21，比 21 大，往后面找

(2) 比較 37, ? 比 37大，比鏈表最大值小，從 37 的下面一層開始找

(3) 比較 71, ?比 71 大，比鏈表最大值小，從 71 的下面一層開始找

(4) 比較 85，比 85 大，從后面找

(5) 比較 117，等于 117，找到了節(jié)點(diǎn)。

具體的搜索算法如下：?

C代碼??

/*?如果存在?x,?返回?x?所在的節(jié)點(diǎn)，?
?*?否則返回?x?的后繼節(jié)點(diǎn)?*/??
find(x)???
{??
????p?=?top;??
????while?(1)?{??
????????while?(p->next->key?<?x)??
????????????p?=?p->next;??
????????if?(p->down?==?NULL)???
????????????return?p->next;??
????????p?=?p->down;??
????}??
}??

跳表的插入

先確定該元素要占據(jù)的層數(shù) K（采用丟硬幣的方式，這完全是隨機(jī)的）

然后在 Level 1 ... Level K 各個(gè)層的鏈表都插入元素。

例子：插入 119， K = 2

如果 K 大于鏈表的層數(shù)，則要添加新的層。

例子：插入 119， K = 4

丟硬幣決定 K

插入元素的時(shí)候，元素所占有的層數(shù)完全是隨機(jī)的，通過一下隨機(jī)算法產(chǎn)生：

C代碼??

int?random_level()??
{??
????K?=?1;??
??
????while?(random(0,1))??
????????K++;??
??
????return?K;??
}??

相當(dāng)與做一次丟硬幣的實(shí)驗(yàn)，如果遇到正面，繼續(xù)丟，遇到反面，則停止，

用實(shí)驗(yàn)中丟硬幣的次數(shù) K 作為元素占有的層數(shù)。顯然隨機(jī)變量 K 滿足參數(shù)為 p = 1/2 的幾何分布，

K 的期望值 E[K] = 1/p = 2. 就是說，各個(gè)元素的層數(shù)，期望值是 2 層。

跳表的高度。

n 個(gè)元素的跳表，每個(gè)元素插入的時(shí)候都要做一次實(shí)驗(yàn)，用來決定元素占據(jù)的層數(shù) K，

跳表的高度等于這?n 次實(shí)驗(yàn)中產(chǎn)生的最大 K，待續(xù)。。。

跳表的空間復(fù)雜度分析

根據(jù)上面的分析，每個(gè)元素的期望高度為 2，一個(gè)大小為 n 的跳表，其節(jié)點(diǎn)數(shù)目的

期望值是 2n。

跳表的刪除

在各個(gè)層中找到包含 x 的節(jié)點(diǎn)，使用標(biāo)準(zhǔn)的 delete from list 方法刪除該節(jié)點(diǎn)。

例子：刪除 71

據(jù)說java.util.concurrent 包里邊有跳表，有時(shí)間要實(shí)踐一下。

轉(zhuǎn)載于:https://www.cnblogs.com/wennian/p/5036909.html

總結(jié)

以上是生活随笔為你收集整理的skiplist 跳表（1）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。