SkipList(跳表)原理及實(shí)現(xiàn)
[導(dǎo)讀]前言 SkipList(跳表)是一個(gè)隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)，可以被看做二叉樹(shù)的一個(gè)變種，它在性能上和紅黑樹(shù)，AVL樹(shù)不相上下，但是跳表的原理非常簡(jiǎn)單，目前在Redis和LeveIDB中都有用到。只要你能熟練操作鏈表，就能輕松實(shí)現(xiàn)一個(gè) 跳表。 如何理解“SkipList”？ 對(duì)于一個(gè)
前言
SkipList(跳表)是一個(gè)隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)，可以被看做二叉樹(shù)的一個(gè)變種，它在性能上和紅黑樹(shù)，AVL樹(shù)不相上下，但是跳表的原理非常簡(jiǎn)單，目前在Redis和LeveIDB中都有用到。只要你能熟練操作鏈表，就能輕松實(shí)現(xiàn)一個(gè) 跳表。
如何理解“SkipList”？
對(duì)于一個(gè)單鏈表來(lái)講，即便鏈表中存儲(chǔ)的數(shù)據(jù)是有序的，如果我們要想在其中查找某個(gè)數(shù)據(jù)，也只能從頭到尾遍歷鏈表。這樣查找效率就會(huì)很低。
上圖是一個(gè)簡(jiǎn)單的有序的單鏈表。
假如對(duì)單鏈表進(jìn)行改造，先對(duì)鏈表中每?jī)蓚€(gè)節(jié)點(diǎn)建立第一級(jí)索引，再對(duì)第一級(jí)索引每?jī)蓚€(gè)節(jié)點(diǎn)建立第二級(jí)索引。如下圖所示：
上面的結(jié)構(gòu)是就是SkipList（跳表）
SkipList（跳表）具有如下性質(zhì)：
1、 由很多層結(jié)構(gòu)組成
2、 每一層都是一個(gè)有序的鏈表
3、 最底層(原始鏈表)的鏈表包含所有元素
4、 如果一個(gè)元素出現(xiàn)在 Level i 的鏈表中，則它在 Level i 之下的鏈表也都會(huì)出現(xiàn)。
5、 每個(gè)節(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指向同一鏈表中的下一個(gè)元素，一個(gè)指向下面一層的元素。
SkipList實(shí)現(xiàn)：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>
#define MAX_LEVEL 15
struct node {
int val;
int max_level;
struct node *forward[MAX_LEVEL];
};
struct skip_list {
struct node head;
int max_level;
int max_level_nodes;
};
void node_init(struct node* node)
{
memset(node, 0, sizeof(struct node));
}
void skip_list_init(struct skip_list* sl)
{
node_init(&sl->head);
sl->max_level = 0;
sl->max_level_nodes = 0;
}
void random_init()
{
static bool done = false;
if (done)
return;
srandom(time(NULL)); //設(shè)種子為隨機(jī)的
done = true;
}
//插入元素獲得層數(shù)，是隨機(jī)產(chǎn)生的
int random_level(void)
{
int i, level = 1;
random_init();
for (i = 1; i < MAX_LEVEL; i++)
if (random() % 2 == 1) //生成的隨機(jī)數(shù)
level++;
return level;
}
void insert(struct skip_list *sl, int val)
{
int level = random_level();
struct node *update[MAX_LEVEL]; //用來(lái)更新每層的指針
struct node *new, *p;
int i;
//申請(qǐng)update空間用于保存每層的指針
new = (struct node*)malloc(sizeof(struct node));
if (!new)
return;
new->max_level = level; //獲取插入元素的隨機(jī)層數(shù)，并更新跳表的最大層數(shù)
new->val = val; //創(chuàng)建當(dāng)前數(shù)據(jù)節(jié)點(diǎn)
for ( i = 0; i < MAX_LEVEL; i++)
update[i] = &sl->head;
//逐層查詢節(jié)點(diǎn)的
p = &sl->head;
for (i = level - 1; i >= 0; i--)
{
//初始化每level層的頭指針
while(p->forward[i] && p->forward[i]->val < val)
p = p->forward[i];
update[i] = p;
}
//逐層更新節(jié)點(diǎn)的指針
for (i = 0; i < level; i++)
{
new->forward[i] = update[i]->forward[i];
update[i]->forward[i] = new;
}
//更新最大層數(shù)
if (sl->max_level < level)
{
sl->max_level = level;
sl->max_level_nodes = 1;
}
else if (sl->max_level == level)
sl->max_level_nodes++;
}
struct node *find(struct skip_list* sl, int val)
{
struct node *node = &sl->head;
int i;
for (i = sl->max_level - 1; i >= 0; i--) {
while (node->forward[i] && node->forward[i]->val < val)
node = node->forward[i];
}
if (node->forward[0] && node->forward[0]->val == val) {
return node->forward[0];
}
else
return NULL;
}
void delete(struct skip_list* sl, int val)
{
struct node *update[MAX_LEVEL]; //用來(lái)更新每層的指針
struct node *p;
int i;
p = &sl->head; //逐層查詢節(jié)點(diǎn)的
for (i = sl->max_level; i >= 0; i--)
{
//初始化每level層的頭指針
while (p->forward[i] && p->forward[i]->val < val)
p = p->forward[i];
update[i] = p;
}
if (p->forward[0] == NULL || p->forward[0]->val != val)
return;
//更新level的層數(shù)
if (p->forward[0]->max_level == sl->max_level)
sl->max_level_nodes--;
for (i = sl->max_level-1; i >= 0; i--)
{
if (update[i]->forward[i] && update[i]->forward[i]->val == val)
update[i]->forward[i] = update[i]->forward[i]->forward[i];
}
if (sl->max_level_nodes == 0)
{
p = &sl->head;
for (i = sl->max_level - 2; i >= 0; i--)
{
while (p->forward[i])
{
sl->max_level_nodes++;
p = p->forward[i];
}
if (sl->max_level_nodes)
{
sl->max_level = i + 1;
break;
} else
sl->max_level = i;
}
}
}
void print_sl(struct skip_list* sl)
{
struct node *node;
int level;
// 從低層到最高層開(kāi)始打印
printf("%d level skip list with %d nodes on top\n",
sl->max_level, sl->max_level_nodes);
for (level = sl->max_level - 1; level >= 0; level--) {
node = &sl->head;
printf("Level[%02d]:", level);
while (node->forward[level]) {
printf("%4d", node->forward[level]->val);
node = node->forward[level];
}
printf("\n");
}
}
int main(int argc,char **argv)
{
struct skip_list sl;
struct node *node = NULL;
int i;
skip_list_init(&sl);
print_sl(&sl);
for (i = 0; i < 10; i++)
insert(&sl, i);
print_sl(&sl);
node = find(&sl, 8);
if (node)
printf("find 8 in sl %d\n", node->val);
else
printf("8 not in sl\n");
for (i = 0; i < 10; i++) {
delete(&sl, i);
print_sl(&sl);
}
return 0;
}
輸出結(jié)果：
如果您覺(jué)得文章對(duì)您有幫助，請(qǐng)分享給更多人
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問(wèn)題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
