SkipList(跳表)原理及实现

时间：2020-05-07 01:01:16

关键字： ST IP BSP LEVEL

[导读]前言 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;
}