跳表学习总结

跳跃表

自我感觉跳跃表就是分层的链表,为了达到二分查找的时间效率,跳跃表提出了层的概念,每一层也是一个链表。

如果能达到第一层的个数是0层的一半,2层的个数是1层的一半,n层的个数是n-1层的一半,并且n层的元素是n-1层的中间数。。即层数最好是lgn(n是元素个数)

为了模拟以上效果,跳跃表采用每个节点随机产生,对于每一层,每两个节点就随机产生多一个层。

对于第一层,每两个节点随机产生多一层的概率是1/2,此时第二层存在的概率是1/2,第二层随机多产生一层的概率是1/2,所以第一层随机多产生两层的概率是1/2*1/2=1/4,以此类推,第一层随机多产生三层的概率是1/8,第一层随机多产生n层的概率是1/2^n...(个人推断,不知是否正确)

所以每次新加入一个节点以1/2^j的概率产生j层,代码如下:

参考随机生成层数

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

另一个算法,参考《算法:C语言实现(第1-4部分)》13.5节:

int randX()

{

    int  i, j, t = rand();

    for(i = 1, j = 2; i < lgNmax; i++,j += j)

        if(t > RAND_MAX / j) break;

    if (i > lgN) lgN = i;

    return i;

}

查找:

每次从最高层向右向下查找

比较的时候的三种情况,以targetNode->next[i]->element和theElement为例:

  • 1.小于:令targetNode = targetNode->next[i]; //第i级链表的下一个

  • 2.大于:向下降级,i- - //不改变targetNode

  • 3.等于:向下降级,i- - //不改变targetNode

参考:跳表

插入

插入的时候需要先查找插入的位置,并且保存数组last[],last[i]表示插入的节点第i层的前一个节点,(保存last数组的目的是要修改层列表,单层列表只需要修改一层,多层列表需要修改多层)

删除

类似插入,也需要保存last[]数组,修改与删除节点相关联的层


redis的跳表每一层多了一个span记录跨度(即我到本层的下一个节点所经历的结点数)

还多了一个后退指针,指向前一个结点

image
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容