数据结构与算法--跳表

跳表是一种各方面性能都比较优秀的动态数据结构,可以支持快速地插入、删除、查找操作,写起来也不复杂,甚至可以替代红黑树(Red-black tree)。

数据结构与算法--跳表
文章图片
跳表.png
这种链表加多级索引的结构,就是 跳表。
【数据结构与算法--跳表】跳表的查找、插入、删除操作的时间复杂度都是 O(logn)。
跳表的空间复杂度是 O(n)。不过,跳表的实现非常灵活,可以通过改变索引构建策略,有效平衡执行效率和内存消耗。虽然跳表的代码实现并不简单,但是作为一种动态数据结构,比起红黑树来说,实现要简单多了。所以很多时候,我们为了代码的简单、易读,比起红黑树,我们更倾向用跳表。
数据结构与算法--跳表
文章图片
跳表的插入.png 参考:
极客时间:《数据结构与算法》王争, 17 | 跳表:为什么Redis一定要用跳表来实现有序集合?

    推荐阅读