SkipList(跳表)原理及實現(xiàn)

時間：2020-05-07 01:01:16

關(guān)鍵字： ST IP BSP LEVEL

手機看文章

掃描二維碼
隨時隨地手機看文章

[導(dǎo)讀]前言 SkipList(跳表)是一個隨機化的數(shù)據(jù)結(jié)構(gòu)，可以被看做二叉樹的一個變種，它在性能上和紅黑樹，AVL樹不相上下，但是跳表的原理非常簡單，目前在Redis和LeveIDB中都有用到。只要你能熟練操作鏈表，就能輕松實現(xiàn)一個跳表。如何理解“SkipList”？對于一個

前言

SkipList(跳表)是一個隨機化的數(shù)據(jù)結(jié)構(gòu)，可以被看做二叉樹的一個變種，它在性能上和紅黑樹，AVL樹不相上下，但是跳表的原理非常簡單，目前在Redis和LeveIDB中都有用到。只要你能熟練操作鏈表，就能輕松實現(xiàn)一個跳表。

如何理解“SkipList”？

對于一個單鏈表來講，即便鏈表中存儲的數(shù)據(jù)是有序的，如果我們要想在其中查找某個數(shù)據(jù)，也只能從頭到尾遍歷鏈表。這樣查找效率就會很低。

上圖是一個簡單的有序的單鏈表。

假如對單鏈表進行改造，先對鏈表中每兩個節(jié)點建立第一級索引，再對第一級索引每兩個節(jié)點建立第二級索引。如下圖所示：

上面的結(jié)構(gòu)是就是SkipList（跳表）

SkipList（跳表）具有如下性質(zhì)：

1、 由很多層結(jié)構(gòu)組成
2、 每一層都是一個有序的鏈表
3、 最底層(原始鏈表)的鏈表包含所有元素
4、 如果一個元素出現(xiàn)在 Level i 的鏈表中，則它在 Level i 之下的鏈表也都會出現(xiàn)。
5、 每個節(jié)點包含兩個指針，一個指向同一鏈表中的下一個元素，一個指向下面一層的元素。

SkipList實現(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è)種子為隨機的
    done = true;
}

//插入元素獲得層數(shù)，是隨機產(chǎn)生的
int random_level(void)
{
    int i, level = 1;

    random_init();

    for (i = 1; i < MAX_LEVEL; i++)
        if (random() % 2 == 1) //生成的隨機數(shù)
            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; //獲取插入元素的隨機層數(shù)，并更新跳表的最大層數(shù)
    new->val = val; //創(chuàng)建當前數(shù)據(jù)節(jié)點

    for ( i = 0; i < MAX_LEVEL; i++)
        update[i] = &sl->head;
    //逐層查詢節(jié)點的
    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é)點的指針
    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]; //用來更新每層的指針
    struct node *p;
    int i;

    p = &sl->head; //逐層查詢節(jié)點的

    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;

    // 從低層到最高層開始打印
    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;
}