力扣(LeetCode)- 跳表(skip list) 收藏 阅读:109
2020-11-24 09:52:55

1. 什么是跳表(skip list)

跳表是由William Pugh发明。他在 Communications of the ACM June 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees,在该论文中详细解释了跳表的数据结构和插入删除操作。

跳表全称为跳跃列表,可以快速查询,插入和删除一个有序连续元素的数据链表。

跳表在查找、插入平均时间复杂度是O(logn),速度很快。我们知道链表的查找的时间复杂度是O(logn)效率较低,而跳表则解决了此问题。

那么跳表是怎么解决的呢?

有序链表需要从头遍历,在链表上建立多层索引,可以通过先查找索引然后确定元素的范围,最后小范围的遍历找到元素。

跳表的空间复杂度O(n),跳表是以空间换时间的思路。向上每级有n/2个节点,依次,最后上层有2个节点。

如下图所示:

image-20201124091522388.png

2. 跳表索引维护

通过前面的讲解,我们知道了跳表如何查找。那么往跳表插入数据,我们该如何维护索引呢?

首先,最底层的链表的插入和链表的插入没有区别,这个就不多讲了。

当我们不断插入链表的数据时候,如果不维护索引,那么两个索引之间有可能聚集大量的数据,跳表的查询效率会降低。在极端的情况下,跳表会退化成单链表。

所以,我们需要用一种方法,来动态更新索引。

红黑树和AVL树都是平衡二叉树,树的大小平衡是通过左旋和右旋的方式来维护。跳表一般通过i 个随机函数的方式来维护索引的平衡性。

当往跳表中插入数据时,通过随机函数生成一个随机值N,那么把该索引添加到从第1级到N级的索引中。从概率学上讲,跳表就不至于性能过度退化,这样就可以使索引平衡了。

但是,随机函数该如何选择呢?这个读者可以自己研究,这里不做讲解了。

3. 跳表的应用

通过前面的讲解,我们知道跳表的优势是查找速速快,且修改的效率高。所以,跳表的应用很广泛,下面我们来举例。

Redis的有序集合(zset)就是通过跳表实现的,支持插入、删除、查找、有序输出所有元素、按照范围检索。

那么Redis 的有序集合为什么不用红黑树实现呢?

因为红黑树在按照范围查找的效率没有跳表的效率高,跳表按照范围查好可以达到O(logn)。


© 版权归知否网(zhifou.net)所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权知否网将依法追究其法律责任。
读后有收获,请作者喝杯咖啡


全部评论

发表评论