跳跃表skiplist原理

github地址:
https://github.com/arkulo56/thought/blob/master/software/algorithm/%E7%AE%97%E6%B3%95---%E8%B7%B3%E8%B7%83%E8%A1%A8(skiplist)%E5%8E%9F%E7%90%86.md

跳跃表(skiplist)原理

跳跃表也是一种数据查找结构,如果红黑树,AVL等一样,不过因为其插入修改的时候不需要做大范围的平衡操作,只需要局部范围的修改指针(锁的范围较小),因此有很多成熟的代码在使用它,例如redis就用它来实现有序集合。

原理

简单的讲,他还是一个list!只不过查找的时候不用一个一个的去遍历元素!

看这个例子,我们给其中的一些元素多加了一个指针,指向当前位置+2的元素,如果要遍历查找,根据上面这层的指针,我们可以减少很多次遍历!!

如果觉得上面这种情况减少的遍历次数还不够,那我们是不是可以多加几层指针,跨度再大一些!!

应该给每个元素加几层?

有些程序是按照算法取随机数,有些程序是在随机算法的基础上再和当前最大层数做比较,那最简单的做法是扔硬币,字朝上就加一层直到花朝上就停止,这就是该元素的层数

操作

说说操作吧,我们就来看看插入操作是如何完成的,其他操作类似。

  1. 首先要确定新增加元素的层数
  2. 如果新添是i层节点,那就从head节点的forword[i]开始向后遍历,做插入的指针修改。记住!这里是操作的重点,这就像一个单链表的插入一样,只不过我们是多个单链表组合在一起。

代码

...稍后补充

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容