两节我们讲了二分查找算法。当时我讲到,因为二分查找底层依赖的是数组随机访问的特性,所以只能用数组来实现。如果数据存储在链表中,就真的没法用二分查找算法了吗?
实际上,我们只需要对链表稍加改造,就可以支持类似“二分”的查找算法。我们把改造之后的数据结构叫作跳表(Skiplist),也就是今天要讲的内容。
跳表这种数据结构对你来说,可能会比较陌生,因为一般的数据结构和算法书籍里都不怎么会讲。但是它确实是一种各方面性能都比较优秀的动态数据结构,可以支持快速的插入、删除、查找操作,
写起来也不复杂,甚至可以替代红黑树(Red-blacktree)。
Redis中的有序集合(Sorted Set)就是⽤跳表来实现的。如果你有一定基础,应该知道红黑树也可以实现快速的插入、删除和查找操作。那Redis为什么会选择用跳表来实现有序集合呢?
为什么不用红黑树呢?学完今天的内容,你就知道答案了。
跳表的实现还是稍微有点复杂的,我将Java实现的代码放到了GitHub中,你可以根据我刚刚的讲解,对照着代码仔细思考⼀下。你不⽤死记硬背代码,跳表的实现并不是我们这节的重点
今天我们讲了跳表这种数据结构。跳表使用空间换时间的设计思路,通过构建多级索引来提高查询的效率,实现了基于链表的“二分查找”。跳表是一种动态数据结构,支持快速的插入、删除、查找操作,时间复杂度都是O(logn)。
跳表的空间复杂度是O(n)。不过,跳表的实现非常灵活,可以通过改变索引构建策略,有效平衡执行效率和内存消耗。虽然跳表的代码实现并不简单,但是作为一种动态数据结构,比起红黑树来说,
实现要简单多了。所以很多时候,我们为了代码的简单、易读,比起红黑树,我们更倾向用跳表。
在今天的内容中,对于跳表的时间复杂度分析,我分析了每两个结点提取一个结点作为索引的时间复杂度。如果每三个或者五个结点提取一个结点作为上级索引,
对应的在跳表中查询数据的时间复杂度是多少呢
如果每三个或者五个节点提取一个节点作为上级索引,那么对应的查询数据时间复杂度,应该也还是 O(logn)。
假设每 5 个节点提取,那么最高一层有 5 个节点,而跳表高度为 log5n,每层最多需要查找 5 个节点,即 O(mlogn) 中的 m = 5,最终,时间复杂度为 O(logn)。
空间复杂度也还是 O(logn),虽然省去了一部分索引节点,但是似乎意义不大。
不知道在一般的生产系统,跳表的提取是按照多少个节点来实现?还是每个系统根据实际情况,都不一样。
看了跳表的 Java 实现,查找部分的代码真是漂亮,插入部分看了半天才看明白。
来源:https://www.icode9.com/content-1-566201.html
联系客服