SkipList(跳表)原理及实现
时间：2020-05-07 01:01:16
手机看文章
扫描二维码
随时随地手机看文章
[导读]前言 SkipList(跳表)是一个随机化的数据结构，可以被看做二叉树的一个变种，它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，目前在Redis和LeveIDB中都有用到。只要你能熟练操作链表，就能轻松实现一个 跳表。 如何理解“SkipList”？ 对于一个
前言
SkipList(跳表)是一个随机化的数据结构，可以被看做二叉树的一个变种，它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，目前在Redis和LeveIDB中都有用到。只要你能熟练操作链表，就能轻松实现一个 跳表。
如何理解“SkipList”？
对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低。
上图是一个简单的有序的单链表。
假如对单链表进行改造，先对链表中每两个节点建立第一级索引，再对第一级索引每两个节点建立第二级索引。如下图所示：
上面的结构是就是SkipList（跳表）
SkipList（跳表）具有如下性质：
1、 由很多层结构组成
2、 每一层都是一个有序的链表
3、 最底层(原始链表)的链表包含所有元素
4、 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。
5、 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。
SkipList实现：
#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)); //设种子为随机的
done = true;
}
//插入元素获得层数，是随机产生的
int random_level(void)
{
int i, level = 1;
random_init();
for (i = 1; i < MAX_LEVEL; i++)
if (random() % 2 == 1) //生成的随机数
level++;
return level;
}
void insert(struct skip_list *sl, int val)
{
int level = random_level();
struct node *update[MAX_LEVEL]; //用来更新每层的指针
struct node *new, *p;
int i;
//申请update空间用于保存每层的指针
new = (struct node*)malloc(sizeof(struct node));
if (!new)
return;
new->max_level = level; //获取插入元素的随机层数，并更新跳表的最大层数
new->val = val; //创建当前数据节点
for ( i = 0; i < MAX_LEVEL; i++)
update[i] = &sl->head;
//逐层查询节点的
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;
}
//逐层更新节点的指针
for (i = 0; i < level; i++)
{
new->forward[i] = update[i]->forward[i];
update[i]->forward[i] = new;
}
//更新最大层数
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]; //用来更新每层的指针
struct node *p;
int i;
p = &sl->head; //逐层查询节点的
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的层数
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;
// 从低层到最高层开始打印
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;
}
输出结果：
如果您觉得文章对您有帮助，请分享给更多人
免责声明：本文内容由21ic获得授权后发布，版权归原作者所有，本平台仅提供信息存储服务。文章仅代表作者个人观点，不代表本平台立场，如有问题，请联系我们，谢谢！
下载文档
