一.skiplist簡介
跳表是由William Pugh發明。他在 Communications of the ACM June 1990, 33(6) 668-676 發表了Skip lists: a probabilistic alternative to balanced trees，在該論文中詳細解釋了跳表的資料結構和插入删除操作。跳躍表使用機率均衡技術而不是使用強制性均衡，是以，對于插入和删除結點比傳統上的平衡樹算法更為簡潔高效。參考算法導論，跳表插入、删除、查找的複雜度均為O(logN)。LevelDB的核心資料結構是用跳表實作的，redis的sorted set資料結構也是用跳表實作的。
下面來研究一下跳表的核心思想：
先從連結清單開始，如果是一個單連結清單，那麼我們知道在連結清單中查找一個元素I的話，需要将整個連結清單周遊一次，時間複雜度為O(n)。
如果是說連結清單是排序的，并且結點中還存儲了指向後面第二個結點的指針的話，那麼在查找一個結點時，僅僅需要周遊N/2個結點即可。因為我們可以先通過每個結點最上面的指針先進行查找，這樣子就能跳過一半的節點。比如我們想查找19，首先和6比較，大于6之後，在和9進行比較，然後在和12進行比較......最後比較到21的時候，發現21大于19，說明查找的點在17和21之間，從這個過程中，我們可以看出，查找的時候跳過了3、7、12等點，是以查找的時間複雜度為O(n/2)（隻是下圖的情況）。
其實，上面基本上就是跳躍表的思想，每一個結點不單單隻包含指向下一個結點的指針，可能包含很多個指向後續結點的指針，這樣就可以跳過一些不必要的結點，進而加快查找、删除等操作。對于一個連結清單内每一個結點包含多少個指向後續元素的指針，這個過程是通過一個随機函數生成器得到，這樣子就構成了一個跳躍表。這就是為什麼論文“Skip Lists : A Probabilistic Alternative to Balanced Trees ”中有“機率”的原因了，就是通過随機生成一個結點中指向後續結點的指針數目。随機生成的跳躍表可能如下圖所示。
如果一個結點存在k個指向後續元素指針的話，那麼稱該結點是一個k層結點。一個跳表的層MaxLevel義為跳表中所有結點中最大的層數。跳表的所有操作均從上向下逐層進行，越上層一次next操作的跨度越大。
二.skiplist原理
為了描述友善，将跳表結構繪畫成如下形式。
跳表結構：
(1) 由多層結構組成
(2) 每一層都是一個有序的連結清單
(3) 最底層(Level 1)的連結清單包含所有元素
(4) 如果一個元素出現在 Level i 的連結清單中，則它在 Level i 之下的連結清單也都會出現。
(5) 每個節點包含兩個指針，一個指向同一連結清單中的下一個元素，一個指向下面一層的元素。
1.跳表的查找
例子：查找元素 117
(1) 比較 21， 比 21 大，往後面找
(2) 比較 37, 比 37大，比連結清單最大值小，從 37 的下面一層開始找
(3) 比較 71, 比 71 大，比連結清單最大值小，從 71 的下面一層開始找
(4) 比較 85， 比 85 大，從後面找
(5) 比較 117， 等于 117， 找到了節點。
2.跳表的插入
1）K小于連結清單的層數
先确定該元素要占據的層數 K（采用丢硬币的方式，這完全是随機的），然後在 Level 1 ... Level K 各個層的連結清單都插入元素。
例子：插入 119， K = 2
2）K大于連結清單的層數
如果 K 大于連結清單的層數，則要添加新的層。
例子：插入 119， K = 4
插入元素的時候，元素所占有的層數完全是随機的，通過某種随機算法産生。
3.跳表的删除
在各個層中找到包含 x 的節點，使用标準的 delete from list 方法删除該節點。
例子：删除 71
三.簡單的skiplist實作
#include<stdio.h>
#include<stdlib.h>
#define MAX_LEVEL 10 //最大層數
//結點
typedef struct nodeStructure
{
int key;
int value;
//指針數組
//定義 int *p[n];[]優先級高，先與p結合成為一個數組，再由int*說明這是一個整型指針數組，它有n個指針類型的數組元素。
//這裡執行p + 1時，則p指向下一個數組元素，這樣指派是錯誤的：p = a；因為p是個不可知的表示，隻存在p[0]、p[1]、p[2]
//...p[n - 1], 而且它們分别是指針變量可以用來存放變量位址。但可以這樣 *p = a; 這裡*p表示指針數組第一個元素的值，
//即a的首位址的值。
//這裡定義了一個變長指針數組，數組中預設隻有一個元素nodeStructure*。使用變長數組（柔性數組）的目的是為了後續對
//該數組擴容，達到動态配置設定記憶體，節約空間的目的。
struct nodeStructure *next[1];
}nodeStructure;
//跳表
typedef struct skiplist
{
int level;
nodeStructure *header;
}skiplist;
//建立結點
nodeStructure* createNode(int level, int key, int value)
{
// nodeStructure::next是一個變長數組，額外配置設定時為什麼是level-1倍呢？
// 因為這裡是為了相容性變長數組聲明為struct nodeStructure *next[1];（也可以用next[0],但是有些編譯器不支援）
// 是以nodeStructure自身已經占了一個，再添加level-1個即可，如果是next[0]的話，就不能減一了。
nodeStructure *ns = (nodeStructure *)malloc(sizeof(nodeStructure) + (level-1)*sizeof(nodeStructure*));
ns->key = key;
ns->value = value;
return ns;
}
//初始化跳表
skiplist* createSkiplist()
{
skiplist *sl = (skiplist *)malloc(sizeof(skiplist));
sl->level = 0;
sl->header = createNode(MAX_LEVEL , 0, 0);
for (int i = 0; i < MAX_LEVEL; i++)
{
sl->header->next[i] = NULL;
}
return sl;
}
//随機産生層數
int randomLevel()
{
int k = 1;
while (rand() % 2)
k++;
k = (k < MAX_LEVEL) ? k : MAX_LEVEL;
return k;
}
//插入節點
bool insert(skiplist *sl, int key, int value)
{
nodeStructure *update[MAX_LEVEL];
nodeStructure *p, *q = NULL;
p = sl->header;
int k = sl->level;
//這裡還是查找插入位置階段，并未開始插入
//從最高層往下，每層都查找插入位置，當周遊到該層的尾部（p->next[i]==NULL）
//也沒有找到比key大的結點時，将該層的最後一個結點的指針放到update[i]中。
//如果在某層中找到了比key大或等于key的結點時，将該結點之前的那個比key小的結點的指針
//放到update[i]中。
//這樣一來，參考（二.skiplist原理中的跳表插入章節圖）,以插入119為例，因為此時k暫時是最大層數，
//update[i]存放的是37、71和117所在結點的指針。
for (int i = k - 1; i >= 0; i--){
while ((q = p->next[i]) && (q->key < key))
{
p = q;
}
update[i] = p;
}
//不能插入相同的key，這裡排除掉了上述等于key的情況。
//此時q是第一層中的某個結點。
if (q&&q->key == key)
{
return false;
}
//産生一個随機層數k
k = randomLevel();
//更新跳表的level，這裡假設k=sl->level+1，參考（二.skiplist原理中的跳表插入章節圖）,以插入119為例，
//update[3]應該直接等于新增那層頭結點的指針，就像下面代碼寫的那樣。
if (k > (sl->level))
{
for (int i = sl->level; i < k; i++){
update[i] = sl->header;
}
sl->level = k;
}
//建立一個待插入結點q，從低到高一層層插入
q = createNode(k, key, value);
//逐層更新結點的指針，和普通連結清單插入一樣
for (int i = 0; i < k; i++)
{
q->next[i] = update[i]->next[i];
update[i]->next[i] = q;
}
return true;
}
//搜尋指定key的value
int search(skiplist *sl, int key)
{
nodeStructure *p, *q = NULL;
p = sl->header;
//從最高層往下開始搜尋
int k = sl->level;
for (int i = k - 1; i >= 0; i--){
while ((q = p->next[i]) && (q->key <= key))
{
if (q->key == key)
{
return q->value;
}
p = q;
}
}
return NULL;
}
//删除指定的key
bool deleteSL(skiplist *sl, int key)
{
nodeStructure *update[MAX_LEVEL];
nodeStructure *p, *q = NULL;
p = sl->header;
//從最高層往下開始搜尋
int k = sl->level;
for (int i = k - 1; i >= 0; i--){
while ((q = p->next[i]) && (q->key < key))
{
p = q;
}
update[i] = p;
}
//這裡和插入類似，隻不過找到該結點後删除
if (q&&q->key == key)
{
//逐層删除，和普通連結清單删除一樣
for (int i = 0; i < sl->level; i++){
if (update[i]->next[i] == q){
update[i]->next[i] = q->next[i];
}
}
free(q);
//如果某些層隻有被删除的這個結點，那麼需要更新跳表的level
for (int i = sl->level - 1; i >= 0; i--){
if (sl->header->next[i] == NULL){
sl->level--;
}
}
return true;
}
else
{
return false;
}
}
//釋放跳表，雖然每個結點分了很多層，單歸根結底是一個結點，是以和單連結清單的釋放是一樣的。
void freeSL(skiplist *sl)
{
if (!sl)
return;
nodeStructure *p, *q = NULL;
p = sl->header;
while (p)
{
q = p->next[0];
free(p);
p = q;
}
free(sl);
}
void printSL(skiplist *sl)
{
//從最高層開始列印
nodeStructure *p, *q = NULL;
int k = sl->level;
for (int i = k - 1; i >= 0; i--)
{
p = sl->header;
while (1)
{
q = p->next[i];
printf("%d -> ", p->value);
p = q;
if (p==NULL)
{
break;
}
}
printf("\n");
}
printf("\n");
}
int main()
{
skiplist *sl = createSkiplist();
printf("插入結點：1<key=value<11\n");
for (int i = 1; i < 11; i++)
{
insert(sl, i, i);
}
printSL(sl);
//搜尋
printf("搜尋key=3的value\n");
int i = search(sl, 3);
printf("搜尋結果value=%d\n",i);
//删除
printf("删除key=3的結點\n");
bool b = deleteSL(sl, 3);
if (b)
{
printf("删除成功\n");
}
printSL(sl);
freeSL(sl);
system("pause");
return 0;
}
運作結果如下，由于K值得随機性，并不是每次的運作結果都是這樣。
參考連結：http://kenby.iteye.com/blog/1187303
參考連結：http://dsqiu.iteye.com/blog/1705530
參考連結：http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html