【数据结构】跳跃列表 SkipList

前端之家收集整理的这篇文章主要介绍了【数据结构】跳跃列表 SkipList前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

SkipList

超高性能数据库redis和levelDB都用到了这种神奇的数据结构:SkipList(跳跃表)。之所以说它神奇,是因为跳跃表是基于一个随机数的。跳跃表是在有序链表的基础上进行了扩展,解决了有序链表结构查找特定值困难的问题(O(logn)),是一种可以替代平衡二叉树的数据结构(查询的时间二者基本相同,但是插入的时间跳跃表优于平衡二叉树)。

相比于各种平衡二叉树,跳跃表的实现比较简单。

有序表的搜索


从这个链表中
寻找23,找2次
寻找43,找4次
寻找59,找6次

怎么优化?链表当然不能二分查找,但可以把一些节点提取出来作为索引,得到下面的结构

把14 24 50 72 提取出来作为一级索引,这样的搜索的时候就可以减少比较次数了。还可以提取出来一个二级索引,变成如下的结构

我们可以看出,这是一种类似树状数组思想的分层链表结构。

跳跃列表

下面的结构就是跳表
其中-1表示INTMIN 链表的最小值 1表示INTMAX链表的最大值。

跳表具有下面的性质
①由很多层结构组成
②每一层都是一个有序的列表
③最底层(Level 1)的链表包含所有元素
④如果一个元素出现在Level i的链表中,则它在Level i之下的链表中也都会出现
⑤每个节点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素

跳表的搜索

从最高层开始找,如果发现下一个元素小于搜索值,那么继续往本层的后一个找。如果发现下一个元素大于搜索值,那么就往当前的下一层找。如果等于 = = 正好。

代码

/*如果存在x 返回x所在的节点 *否则返回x的后继节点*/
find(x)
{
    p = top;
    while(true) {
        while(p->next->key < x) p = p->next;
        if(p->down == NULL) return p->next;
        p = p->down;
    }
}

跳表的插入

先确定该元素要占据的层数K(这是一个随机数)
然后再Level 1…k 各个层的链表都插入元素

比如K(119) = 2的情况

比如插入119,K=4

“丢硬币”决定K

插入元素的时候,元素所占有的层数完全是随机的,通过以下的随机算法产生:

int random_level()
{
    k = 1;
    while(random(0,1)) k ++;
    return k;
}

相当于做一次丢硬币的实验,如果正面则继续丢,遇到反面则停止。
用试验中丢硬币的次数K作为元素占有的层数。显然随机变量K满足参数为p=1/2的几何分布。
K的期望值E[K]=1/p=2 就是说,各个元素的层数期望值是2层。

跳表的高度

n个元素的跳表,每个元素插入的时候都要做一次实验,用来决定元素占据的层数K. 跳表的高度等于这N次实验中产生的最大K。

跳表的空间复杂度

每个元素的期望高度为2,一个大小为n的跳表,其节点数目的期望值是2n

跳表的删除

在每个层中找到包含x的节点,使用标准的delete form list方法删除该节点

比如,删除 71

原文链接:https://www.f2er.com/datastructure/382636.html

猜你在找的数据结构相关文章