今天有同學(xué)去面試，被問到了“跳表”這種數(shù)據(jù)結(jié)構(gòu)，說實(shí)話我之前對(duì)它了解不多，于是上網(wǎng)查了跳表的資料，并在這里總結(jié)一下。
什么是跳表？要說清楚這個(gè)問題，我們就要先從普通的有序鏈表說起。一個(gè)普通有序列表的結(jié)構(gòu)如下：
我們可以看到，上圖所示的鏈表按照由小到大的順序排列（-1表示最小值，1表示最大值，這是本文的一個(gè)約定），如果我們想要查找一個(gè)元素x，算法如下：
1
2
3
| cell *p = head;
while (p->next->key < x) p=p->next;
return p; |
上面這個(gè)算法得到了x元素的前驅(qū)或者所有大于x的元素中最小的一個(gè)元素。
基于上面這個(gè)鏈表，我們想要插入一個(gè)元素35的算法是：
1
2
3
4
5
| p = find(35)
cell *p1 = (cell *) malloc(sizeof(cell));
p1->key=35;
p1->next = p->next ;
p->next = p1 ; |
想要?jiǎng)h除元素37的算法是：
1
2
3
4
| p=find(37);
CELL *p1 =p->next;
p->next = p1->next ;
free(p1); |
我想這些算法大家都應(yīng)該是耳熟能詳了，對(duì)于這樣一個(gè)鏈表，查找、刪除、插入一個(gè)元素的時(shí)間復(fù)雜度都是O(n)。
*********************我是分割線************************
好，下面我們正式開始介紹跳表。跳表是個(gè)概率性數(shù)據(jù)結(jié)構(gòu)，可以被看作是二叉樹的一個(gè)變種。跳表是由William Pugh在1990年發(fā)明的。它是一種用戶維護(hù)有序元素的數(shù)據(jù)結(jié)構(gòu)。
跳表的構(gòu)造過程是：
1、給定一個(gè)有序的鏈表。
2、選擇連表中最大和最小的元素，然后從其他元素中按照一定算法隨即選出一些元素，將這些元素組成有序鏈表。這個(gè)新的鏈表稱為一層，原鏈表稱為其下一層。
3、為剛選出的每個(gè)元素添加一個(gè)指針域，這個(gè)指針指向下一層中值同自己相等的元素。Top指針指向該層首元素
4、重復(fù)2、3步，直到不再能選擇出除最大最小元素以外的元素。
一個(gè)跳表，應(yīng)該具有以下特征：
- 一個(gè)跳表應(yīng)該有幾個(gè)層（level）組成；
- 跳表的第一層包含所有的元素；
- 每一層都是一個(gè)有序的鏈表；
- 如果元素x出現(xiàn)在第i層，則所有比i小的層都包含x；
- 第i層的元素通過一個(gè)down指針指向下一層擁有相同值的元素；
- 在每一層中，-1和1兩個(gè)元素都出現(xiàn)(分別表示INT_MIN和INT_MAX)；
- Top指針指向最高層的第一個(gè)元素。
讓我們用一個(gè)跳表來重新構(gòu)建文章開頭的有序鏈表：
通過圖我們可以看出，整個(gè)跳表分為三層，每一層都是一個(gè)有序鏈表，第一層包含所有的元素。top指針指向最高層的-1元素，較高層的元素都能在較低的層里找到，并且較高層的元素含有一個(gè)指針指向下一層值相同的元素。
上面的特征和圖基本就給出了一個(gè)跳表的定義和結(jié)構(gòu)。至于哪些元素應(yīng)該再更高一層中保留，我們會(huì)在下面敘述。
在結(jié)構(gòu)清晰之后，我們需要明白的是跳表為什么要這樣設(shè)計(jì)？這么存儲(chǔ)的好處是什么呢？讓我們通過對(duì)跳表操作來尋找答案。
首先是查找操作。在跳表中查找一個(gè)元素x的算法如下：
1
2
3
4
5
6
| p=top
While(1){
while (p->next->key < x ) p=p->next;
If (p->down == NULL ) return p->next
p=p->down ;
} |
接著是插入算法。假設(shè)要插入一個(gè)元素“119”，我們?cè)O(shè)定需要插入該元素的層數(shù)為“k”（即我們需要在所有的[1,k]范圍內(nèi)的層里都插入元素。k的值我們會(huì)在下文中敘述），則插入算法是：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| int insert(val x){
int i;
int j = n; //n是當(dāng)前表所擁有的level數(shù)
cell *p[k]; //指針數(shù)組，用來保存每一層要插入元素的前驅(qū)
cell *p1;
p1 = top->next;
while(p1){
while(p1->next->val < x) p1=p1->next;
if(j <= k){
p[j-1] = p1; //保存每一層的指針
p1 = p1->down; //指向下一層
j--;
}
}
//下面的代碼是將x插入到各層
for (i = 0; i<k; i++){
if(p[i]==NULL){//k>n的情況，需要?jiǎng)?chuàng)建一個(gè)層
//創(chuàng)建層的第一個(gè)元素，并將top指向它
cell *elementhead = (cell *) malloc(sizeof(cell));
element->val = -1;
element->down = top;
top = elementhead;
//創(chuàng)建最后一個(gè)元素
cell *elementtail = (cell *) malloc(sizeof(cell));
elementtail->val = 1;
elementtail->next = elementtail->down = NULL;
//在該層中創(chuàng)建并插入x
cell *element = (cell *) malloc(sizeof(cell));
element->val = x;
elementhead->next = element;
element->next = elementtail;
element->down = p[i-1]->next;
}
//正常插入一個(gè)元素
cell *element = (cell *) malloc(sizeof(cell));
element->val = x;
element->next = p[i]->next;
element->down = (i=0?NULL:(p[i-1]->next));
p[i]->next = element;
}
return 0;
} |
最后是刪除操作。刪除一個(gè)元素x，如果x被刪除后某層只剩下頭尾兩個(gè)節(jié)點(diǎn)，則刪除這一層。具體算法如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| int delete(val x){
int i = n; //n表示當(dāng)前總層數(shù)
cell *p, *p1;
p = top;
while(n>0){
while(p->next->val < x) p=p->next;
if(p->next->val == x){//假如當(dāng)前層存在節(jié)點(diǎn)x,刪除
if(p = top && p->next->next->val == INT_MAX){//該層之存在一個(gè)節(jié)點(diǎn)
top = p->down;
free(p->next->next);
free(p->next);
free(p);
p = top;
}
else{
p1 = p->next;
p->next = p1->next;
free(p1);
}
}
p = p->down;
n--;
}
} |
好了，我們可以看到，無論查找、插入、刪除，跳表的時(shí)間復(fù)雜度都是O(lgn)！這就是為什么我們要引入跳表。
最后，讓我們來闡述哪些元素應(yīng)該在上一層保留，以及插入操作時(shí)確定插入元素的層數(shù)k。
哪些元素應(yīng)該在高層保留，是隨機(jī)決定的。具體算法如下：
我們假定一個(gè)函數(shù)rand()，隨機(jī)返回1或者0
假設(shè)元素i最多在第k層保留
k的值由程式“ while(rand()) k++;”來決定
看明白了么？也就是從第一層隨機(jī)選出一些元素放到第二層，再從第二層隨機(jī)選出元素放到第三層，以此類推，知道沒有元素再被選出。插入操作時(shí)被插入元素的層數(shù)也是這么得來的。
本文參考資料：http://www./algorithm/SL.ppt
