美文网首页
改造链表支持"二分查找"

改造链表支持"二分查找"

作者: leejnull | 来源:发表于2020-03-09 17:08 被阅读0次

    改造之后的数据结构叫做跳表,支持类似”二分“的查找算法。

    怎么提高链表查找效率?

    正常链表的查询,因为要从头开始遍历,所以时间复杂度是O(n)。

    截屏2020-03-09下午2.44.51.png

    试想一下给链表建立一个索引,我们先按照每2个节点提取1个节点,那么就可
    以建立这样的节点索引

    截屏2020-03-09下午2.50.52.png

    如果我们要查找某个节点,比如8,我们可以现在第一层索引遍历,找到8所在的区间节点,8比节点7大,比9节点小,那么从7的down指针找到原链表这一层,继续往后遍历就找到8所在的节点位置了。这样,原来如果查找8需要遍历8个节点,现在只需要遍历5个节点。

    我们还可以在第一层的索引基础上,继续按每两个节点抽取一个节点来建立索引。

    截屏2020-03-09下午2.55.24.png

    跳表查询有多快?

    按每两个节点抽一个节点来算,第一级索引的节点个数为:n_2,第二级的节点个数为:n/4,以此类推,第k级的节点个数为:n_(2^k)。
    假设索引有h级,最高级的索引有2个节点,则可以得到这样一个公式:

    n/(2^h) = 2
    =>
    h = log(2)n - 1
    

    如果包含原始链这一层,那么h的高度就是log(2)n。
    如果每一层都要遍历m个节点,那么跳表中查询一个数据的时间复杂度为O(m*logn)。

    那么m的值是多少呢?

    按照前面每2个取1一个节点的规则,那么m的值应为3。当遍历到某个层级的某个节点x时,除了要和x比较,还要和x的下一级节点y比较,如果在x和y之间,那么到x的down指向的下一级,根据之前的规则,x和y分别对应的下一级节点之间只有一个节点,所以每一层最多只需要遍历3个。

    所以,在跳表中,查询一个数据的时间复杂度为O(logn),和二分查找的时间复杂度是一样的。

    跳表消耗多少内存?

    我觉得所有时间复杂度低的算法,在空间复杂度上一定是有抵消的。跳表也是如此,它查询快的原因,是建立在增加了很多层索引的基础上。每层索引的节点数减半,知道减少到2个节点为止,就是一个等比数列。

    原始链表大小为n,每2个节点抽1个节点,每层索引的节点数为:
    n/2, n/4, n/8, ..., 8, 4, 2 
    

    节点总和就是

    n/2+n/4+n/8…+8+4+2 = n-2
    

    也就是说,我们需要额外增加n个节点的空间。

    关于跳表的插入和删除

    关于插入操作和链表是一样的,都是O(1)的时间复杂度,区别在于定位的查找上,跳表在查找上是O(logn)的时间复杂度,而链表是O(n)。
    关于删除,跳表不光要删除原链表中的,还需要删除索引中的。

    跳表索引动态更新

    如果我们不停的往跳表中插入数据,不更新索引,就又可能出现某2个节点间数据非常多的情况下,极端情况下,还会退化成单链表。
    所以需要某种手段来维护索引与原始链表大小间的平衡,如果链表中节点多了,索引节点就相应增加。
    和红黑树、AVL树这样的平衡二叉树,通过左右旋的方式保持左右子树的大小平衡不同,跳表是通过随机函数来维护前面提到的”平衡性“。

    当我们往跳表中插入数据的时候,通过一个随机函数,来决定将这个节点插入到哪几级索引中,比如随机函数生成了值K,就将这个节点添加到第1级到第k级的索引中。

    截屏2020-03-09下午4.13.06.png

    这里的随机函数选择,以后再研究。。。

    Redis为什么要用跳表来实现有序集合,而不是红黑树

    Redis中的有序集合支持的核心操作主要有下面这几个:

    • 插入一个数据
    • 删除一个数据
    • 查找一个数据
    • 按照区间查找数据
    • 迭代输出有序序列

    其中插入、删除、查找以及迭代输出有序序列红黑树也可以完成,效率是一样的,但是按照区间查找这个操作,跳表可以做到O(logn)的时间复杂度定位区间的起点,然后在原始链表中顺序往后遍历就可以了,非常高效。

    而且,跳表更容易代码实现,相比红黑树来说更易懂,跳表更加灵活,可以通过改变索引构建策略,有效平衡执行效率和内存消耗。

    来自https://leejnull.github.io/2020/03/09/2020-03-09-02/

    相关文章

      网友评论

          本文标题:改造链表支持"二分查找"

          本文链接:https://www.haomeiwen.com/subject/niipdhtx.html