什么是跳表

跳表是一種有序的數(shù)據(jù)結(jié)構(gòu)，它通過(guò)在每個(gè)節(jié)點(diǎn)中維持多個(gè)指向其它節(jié)點(diǎn)的指針，從而達(dá)到快速訪問(wèn)的目的。

核心思想

image.png

這是一個(gè)單向鏈表，我們要查詢鏈表中某個(gè)元素的話，需要遍歷整條鏈，所以鏈表查詢的時(shí)間復(fù)雜度為O(N)。

O(N)，這個(gè)時(shí)間復(fù)雜度比較高，查詢效率較低，于是就有人試圖優(yōu)化。

其中，William Pugh 受到二分查找的啟發(fā)，就思考能不能通過(guò)二分法來(lái)跳過(guò)部分節(jié)點(diǎn)，直接鎖定目標(biāo)。于是，他做出了這樣的假設(shè)。

如果是說(shuō)鏈表是排序的，并且節(jié)點(diǎn)中還存儲(chǔ)了指向前面第二個(gè)節(jié)點(diǎn)的指針的話，那么在查找一個(gè)節(jié)點(diǎn)時(shí)，僅僅需要遍歷N/2個(gè)節(jié)點(diǎn)即可。

image.png

同理，如果節(jié)點(diǎn)中還存儲(chǔ)指向前面第四個(gè)節(jié)點(diǎn)的指針的話，那么查找下一個(gè)節(jié)點(diǎn)時(shí)，僅僅需要遍歷N/4個(gè)節(jié)點(diǎn)。

image.png

其實(shí)，這只是理想狀態(tài)下的跳表。

在這種理想狀態(tài)下，每次插入或者刪除節(jié)點(diǎn)時(shí)，新節(jié)點(diǎn)前面的所有節(jié)點(diǎn)都要重新關(guān)聯(lián)，這顯然不是我們想要的結(jié)果。

現(xiàn)實(shí)中的跳表是這樣的。

image.png

跳表的性質(zhì)

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

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

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

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

跳表的結(jié)構(gòu)

跳躍表的節(jié)點(diǎn)有三部分構(gòu)成：key值，value值，以及指向前向節(jié)點(diǎn)的指針數(shù)組，指針數(shù)組的大小由該節(jié)點(diǎn)的層數(shù)決定。

image.png

所以，節(jié)點(diǎn)的數(shù)據(jù)類型可以定義為

typedef struct nodeStructure {
    keyType key; // key值
    valueType value;  // value值
    node forward[1];  // 向前指針數(shù)組，根據(jù)該節(jié)點(diǎn)層數(shù)的不同指向不同大小的數(shù)組
};

定義跳表數(shù)據(jù)類型：

typedef struct listStructure {
   int level; // 跳表的層數(shù)
   struct nodeStructure * header; // 指向header節(jié)點(diǎn)的指針
   } * list; 

跳表的操作

查詢

對(duì)于下圖這個(gè)鏈表結(jié)構(gòu)，假設(shè)我們要查詢值為56的節(jié)點(diǎn)，我們需要比較10次。

image.png

使用跳表優(yōu)化過(guò)的查詢算法，我們只需要比較3次。

image.png

插入

同鏈表類似。

刪除

同鏈表類似。

性能對(duì)比

我們對(duì)跳躍表、平衡樹等進(jìn)行比較，如下圖()所示：

圖片來(lái)自網(wǎng)絡(luò)，未找到原出處