跳表──没听过但很犀利的数据结构

栏目: 数据库 · 发布时间: 6年前

内容简介:跳表(skip list) 对标的是平衡树(AVL Tree),是一种 插入/删除/搜索 都是首先,跳表处理的是有序的链表(一般是双向链表,下图未表示双向),如下:这个链表中,如果要搜索一个数,需要从头到尾比较每个元素是否匹配,直到找到匹配的数为止,即时间复杂度是 $O(n)$。同理,插入一个数并保持链表有序,需要先找到合适的插入位置,再执行插入,总计也是 $O(n)$ 的时间。

跳表(skip list) 对标的是平衡树(AVL Tree),是一种 插入/删除/搜索 都是 O(log n) 的数据结构。它最大的优势是原理简单、容易实现、方便扩展、效率更高。因此在一些热门的项目里用来替代平衡树,如 redis, leveldb 等。

首先,跳表处理的是有序的链表(一般是双向链表,下图未表示双向),如下:

跳表──没听过但很犀利的数据结构

这个链表中,如果要搜索一个数,需要从头到尾比较每个元素是否匹配,直到找到匹配的数为止,即时间复杂度是 $O(n)$。同理,插入一个数并保持链表有序,需要先找到合适的插入位置,再执行插入,总计也是 $O(n)$ 的时间。

那么如何提高搜索的速度呢?很简单,做个索引:

跳表──没听过但很犀利的数据结构

如上图,我们新创建一个链表,它包含的元素为前一个链表的偶数个元素。这样在搜索一个元素时,我们先在上层链表进行搜索,当元素未找到时再到下层链表中搜索。例如搜索数字 19 时的路径如下图:

跳表──没听过但很犀利的数据结构

先在上层中搜索,到达节点 17 时发现下一个节点为 21 ,已经大于 19 ,于是转到下一层搜索,找到的目标数字 19

我们知道上层的节点数目为 $n/2$,因此,有了这层索引,我们搜索的时间复杂度降为了:$O(n/2)$。同理,我们可以不断地增加层数,来减少搜索的时间:

跳表──没听过但很犀利的数据结构

在上面的 4 层链表中搜索 25 ,在最上层搜索时就可以直接跳过 21 之前的所有节点,因此十分高效。

更一般地,如果有 $k$ 层,我们需要的搜索次数会小于 $\lceil \frac{n}{2^k} \rceil + k$ ,这样当层数 $k$ 增加到 $\lceil \log_{2} n \rceil$ 时,搜索的时间复杂度就变成了 $\log n$。其实这背后的原理和二叉搜索树或二分查找很类似,通过索引来跳过大量的节点,从而提高搜索效率。

上节的结构是“静态”的,即我们先拥有了一个链表,再在之上建了多层的索引。但是在实际使用中,我们的链表是通过多次插入/删除形成的,换句话说是“动态”的。上节的结构要求上层相邻节点与对应下层节点间的个数比是 1:2 ,随意插入/删除一个节点,这个要求就被被破坏了。

因此跳表(skip list)表示,我们就不强制要求 1:2 了,一个节点要不要被索引,建几层的索引,都在节点插入时由抛硬币决定。当然,虽然索引的节点、索引的层数是随机的,为了保证搜索的效率,要大致保证每层的节点数目与上节的结构相当。下面是一个随机生成的跳表:

跳表──没听过但很犀利的数据结构

可以看到它每层的节点数还和上节的结构差不多,但是上下层的节点的对应关系已经完全被打破了。

现在假设节点 17 是最后插入的,在插入之前,我们需要搜索得到插入的位置:

跳表──没听过但很犀利的数据结构

接着,抛硬币决定要建立几层的索引,伪代码如下:

randomLevel()
    lvl := 1
    -- random() that returns a random value in [0...1)
    while random() < p and lvl < MaxLevel do
        lvl := lvl + 1
    return lvl

上面的伪代码相当于抛硬币,如果是正面( random() < p )则层数加一,直到抛出反面为止。其中的 MaxLevel 是防止如果运气太好,层数就会太高,而太高的层数往往并不会提供额外的性能,一般 $MaxLevel = \log_{1/p}{n}$。现在假设 randomLevel 返回的结果是 2 ,那么就得到下面的结果。

跳表──没听过但很犀利的数据结构

如果要删除节点,则把节点和对应的所有索引节点全部删除即可。当然,要删除节点时需要先搜索得到该节点,搜索过程中可以把路径记录下来,这样删除索引层节点的时候就不需要多次搜索了。

显然,在最坏的情况下,所有节点都没有创建索引,时间复杂度为$O(n)$,但在平均情况下,搜索的时间复杂度却是 $O(\log n)$,为什么呢?

一些严格的证明会涉及到比较复杂的概率统计学知识,所以这里只是简单地说明。

上面我们提到 MaxLevel原版论文 中用 L(n) 来表示,要求 L(n) 层有 1/p 个节点,在搜索时可以不理会比 L(n) 更高的层数,直接从 L(n) 层开始搜索,这样效率最高。

直观上看,第 $l$ 层的节点中在第 $l+1$ 层也有索引的个数是 $n_{l+1} = n_l p$ 因此第 $l$ 层的节点个数为:

$$ n_l = n p^{l-1} $$

于是代入 $n_{L(n)} = 1/p$ 得到 $L(n) = \log_{1/p}n$。

上面推导到每层的节点数目,直观上看,如果某一层的节点数目小于等于 1,则可以认为它是最高层了,代入 $np^{l-1} = 1$ 得到层数 $L_{max} = \log_{1/p}n + 1 = L(n) + 1 = O(\log n)$。

实际上这个问题并没有直接的解析解,我们能知道的是,当 $n$ 足够大时,最大能达到的层数为 $O(\log n)$,详情可以参见我的另一篇博客最高楼层问题。

为了计算搜索的时间复杂度,我们可以将查找的过程倒过来,从搜索最后的节点开始,一直向左或向上,直到最顶层。如下图,在路径上的每一点,都可能有两种情况:

跳表──没听过但很犀利的数据结构
p
1-p

于是,设 C(k) 为反向搜索爬到第 k 层的平均路径长度,则有:

C(0) = 0
C(k) = p * (情况1) + (1-p) * (情况2)

将两种情况也用 C 代入,有:

C(k) = p*(1 + C(k–1)) + (1–p)*(1 + C(k))
C(k) = C(k–1) + 1/p
C(k) = k/p

上式表明,搜索时,平均在每层上需要搜索的路径长度为 $1/p$,从平均的角度上和我们第一小节构造的“静态”结构相同(p 取 1/2 )。

又注意到,上小节我们知道跳表的最大层数为 $O(\log n)$,因此,搜索的复杂度 $O(\log n) / p = O(\log n)$。

P.S. 这里我们用到的是最大层数,原论文证明时用到的是 $L(n)$,然后再考虑从 $L(n)$ 层到最高层的平均节点个数。这里为了理解方便不再详细证明。

  1. 各种搜索结构提高效率的方式都是通过空间换时间得到的。
  2. 跳表最终形成的结构和搜索树很相似。
  3. 跳表通过随机的方式来决定新插入节点来决定索引的层数。
  4. 跳表搜索的时间复杂度是 $O(\log n)$,插入/删除也是。

想到快排(quick sort)与其它 排序 算法(如归并排序/堆排序)虽然时间复杂度是一样的,但复杂度的常数项较小;跳表的原论文也说跳表能提供一个常数项的速度提升,因此想着常数项小是不是随机算法的一个特点?这也它们大放异彩的重要因素吧。


以上所述就是小编给大家介绍的《跳表──没听过但很犀利的数据结构》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Python编程初学者指南

Python编程初学者指南

[美]Michael Dawson / 王金兰 / 人民邮电出版社 / 2014-10-1

Python是一种解释型、面向对象、动态数据类型的高级程序设计语言。Python可以用于很多的领域,从科学计算到游戏开发。 《Python编程初学者指南》尝试以轻松有趣的方式来帮助初学者掌握Python语言和编程技能。《Python编程初学者指南》共12章,每一章都会用一个完整的游戏来演示其中的关键知识点,并通过编写好玩的小软件这种方式来学习编程,引发读者的兴趣,降低学习的难度。每章最后都会......一起来看看 《Python编程初学者指南》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码