20?張圖擊潰，跳表！

跳躍鏈表及其應(yīng)用是非常熱門的問題，面試時(shí)也非常常問，深入了解其中奧秘大有裨益，不吹了，直接開始！

跳躍鏈表的基本概念

初識(shí)跳表

跳躍列表是一種數(shù)據(jù)結(jié)構(gòu)。它允許快速查詢一個(gè)有序連續(xù)元素的數(shù)據(jù)鏈表。跳躍列表的平均查找和插入時(shí)間復(fù)雜度都是O(log n)，優(yōu)于普通隊(duì)列的O(n)。

跳躍列表由威廉·普發(fā)明，發(fā)明者對(duì)跳躍列表的評(píng)價(jià)：跳躍鏈表是在很多應(yīng)用中有可能替代平衡樹而作為實(shí)現(xiàn)方法的一種數(shù)據(jù)結(jié)構(gòu)。

跳躍列表的算法有同平衡樹一樣的漸進(jìn)的預(yù)期時(shí)間邊界，并且更簡(jiǎn)單、更快速和使用更少的空間。

這種數(shù)據(jù)結(jié)構(gòu)是由William Pugh(音譯為威廉·普)發(fā)明的，最早出現(xiàn)于他在1990年發(fā)表的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。

我在谷歌上找到一篇作者關(guān)于跳表的論文，感興趣強(qiáng)烈建議下載閱讀：

https://epaperpress.com/sortsearch/download/skiplist.pdf

看下這篇論文的摘要部分：

從中我們獲取到的信息是：跳表在動(dòng)態(tài)查找過程中使用了一種非嚴(yán)格的平衡機(jī)制來讓插入和刪除都更加便利和快捷，這種非嚴(yán)格平衡是基于概率的，而不是平衡樹的嚴(yán)格平衡。

說到非嚴(yán)格平衡，首先想到的是紅黑樹RbTree，它同樣采用非嚴(yán)格平衡來避免像AVL那樣調(diào)整樹的結(jié)構(gòu)，這里就不展開講紅黑樹了，看來跳表也是類似的路子，但是是基于概率實(shí)現(xiàn)的。

動(dòng)態(tài)查找的數(shù)據(jù)結(jié)構(gòu)

所謂動(dòng)態(tài)查找就是查找的過程中存在元素的刪除和插入，這樣就對(duì)實(shí)現(xiàn)查找的數(shù)據(jù)結(jié)構(gòu)有一定的挑戰(zhàn)，因?yàn)樵诿看蝿h除和插入時(shí)都要調(diào)整數(shù)據(jù)結(jié)構(gòu)，來保持秩序。

可以作為查找數(shù)據(jù)結(jié)構(gòu)的包括：

• 線性結(jié)構(gòu)：數(shù)組、鏈表
• 非線性結(jié)構(gòu)：平衡樹

來分析一下各種數(shù)據(jù)結(jié)構(gòu)在應(yīng)對(duì)動(dòng)態(tài)查找時(shí)的優(yōu)劣吧！

數(shù)組結(jié)構(gòu)

數(shù)組結(jié)構(gòu)簡(jiǎn)單內(nèi)存連續(xù)，可以實(shí)現(xiàn)二分查找等基于下標(biāo)的操作，我一直認(rèn)為數(shù)組的殺手锏就是下標(biāo)，連續(xù)的內(nèi)存也帶來了問題。

當(dāng)進(jìn)行插入和刪除時(shí)就面臨著整體的調(diào)整，就像在火車站排隊(duì)買票，隊(duì)頭走一個(gè)整個(gè)隊(duì)伍向前挪一步，有加塞的后面的又整體向后挪一步，這種整體移動(dòng)操作在數(shù)組結(jié)構(gòu)中性能損耗很大，并且在大數(shù)據(jù)量時(shí)對(duì)連續(xù)內(nèi)存要求很高，當(dāng)然這個(gè)在大內(nèi)存機(jī)器上可能沒有什么問題。

如圖插入6和刪除5時(shí) 數(shù)組元素的移動(dòng)：

鏈表結(jié)構(gòu)

鏈表結(jié)構(gòu)也比較簡(jiǎn)單，但是不要求內(nèi)存連續(xù)，不連續(xù)也就沒有下標(biāo)可以加速，但是鏈表在執(zhí)行刪除和插入時(shí)影響的只是插入刪除點(diǎn)的前后元素，影響非常小。

但是每次查找元素是需要進(jìn)行遍歷，就算我知道某個(gè)元素一定在大致的什么位置，也只能一步步走過去，看到這里要覺得有優(yōu)化的空間，那你也蠻厲害的了，說不定早幾年跳表就是你的發(fā)明了。

如圖刪除元素5和插入元素49時(shí)的處理：

平衡樹

平衡樹也是處理動(dòng)態(tài)查找問題的一把好手，樹一般是基于鏈表實(shí)現(xiàn)的，只不過樹的節(jié)點(diǎn)之間并不是鏈表簡(jiǎn)單的線性關(guān)系，會(huì)有兄弟姐妹父親等節(jié)點(diǎn)，并且各個(gè)層級(jí)有數(shù)量的限制，可以看到樹其實(shí)還是蠻復(fù)雜的。

節(jié)點(diǎn)需要存儲(chǔ)的信息很多，各個(gè)指針指來指去，復(fù)雜的結(jié)構(gòu)增加了調(diào)整平衡性的難度，不同情況下的左旋右旋，所以出現(xiàn)了紅黑樹這種工程版本的AVL，但是在實(shí)際場(chǎng)景中可能并不需要這些兄弟姐妹父親關(guān)系，有種殺雞宰牛刀的意味了。

紅黑樹的節(jié)點(diǎn)結(jié)構(gòu)定義：

#define?COLOR_RED??0x0
#define?COLOR_BLACK?0x1

typedef?struct?RBNode{
???int?key;
???unsigned?char?color;
???struct?RBNode?*left;
???struct?RBNode?*right;
???struct?RBNode?*parent;
}rb_node_t,?*rb_tree_t;
另外紅黑樹調(diào)整屬性過程中插入分為3種情況，刪除分為4種情況，還是比較難以理解的，除非你穿紅上衣