分类：跳表

2021
11-09

python实现跳表SkipList的示例代码

跳表跳表，又叫做跳跃表、跳跃列表，在有序链表的基础上增加了“跳跃”的功能，由WilliamPugh于1990年发布，设计的初衷是为了取代平衡树（比如红黑树）。Redis、LevelDB都是著名的Key-Value数据库，而Redis中的SortedSet、LevelDB中的MemTable都用到了跳表。对比平衡树，跳表的实现和维护会更加简单，跳表的搜索、删除、添加的平均时间复杂度是O(logn)。跳表的结构如图所示：可以发现，对于一个节点Node，其含有多个next... 继续阅读 >

2020
10-09

c++如何实现跳表（skiplist）

引言二分查找底层依赖的是数组随机访问的特性，所以只能用数组来实现。如果数据存储在链表中，就真的没法用二分查找算法了吗？实际上，只需要对链表稍加改造，就可以支持类似“二分”的查找算法。改造之后的数据结构叫作跳表。定义跳表是一个随机化的数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(logn)，优于普通队列的O(n)。性能上和红黑树，AVL树不相上下，但跳表的原理非常... 继续阅读 >