跳表

参考 https://zhuanlan.zhihu.com/p/68516038 跳表插入、删除、查找元素的时间复杂度跟红黑树都是一样量级的，时间复杂度都是 O (logn)。

1 什么是跳表

• 跳表是建立在 有序单链表 基础上的，无序链表无法构建跳表。 跳表相当于在原链表上增加了多级索引，每一级索引都是链式结构。查询时从最上面一级索引开始，如果能直接匹配那么通过节点访问数据；如果没有匹配，通过判断 key 大小进入下一级索引查询，按此方式直到查询成功。

2 总结

1. 跳表是可以实现二分查找的有序链表；
2. 每个元素插入时随机生成它的 level；
3. 最底层包含所有的元素；
4. 如果一个元素出现在 level(x)，那么它肯定出现在 x 以下的 level 中；
5. 每个索引节点包含两个指针，一个向下，一个向右；
6. 跳表查询、插入、删除的时间复杂度为 O(log n)，与平衡二叉树接近；