TOC
跳跃表（skiplists）
跳跃表是一种增强版的链表，他能在O(lgn)的时间内完成搜索。
首先，我们熟知的链表本身具有的特性就是容易删除与增加，但是在搜索的时候会使用O(n)的时间。主要的原因就是链表本身访问起来必须的连续的，也许我们可能在某个节点上打出更多的锚点以链接到更远的节点，但是这样整个链表将会变得非常复杂，所以我们今天将要学习一种简单，但十分有效的数据结构，跳跃表。
结构
首先盗个图看看，懒得画了
跳跃表是一个多层相互链接的链表组，其中，L1 是基础链表，他将拥有链表中的所有元素，越向上的层级会拥有更少的元素，并且最优情况是每层元素数量是上一层二分之一。当然其分布绝对是越平均越好。
搜索
跳跃表的搜索从最高层开始不断往右搜索，直到发现过了头，接着回到上一个节点 向下一个层级 继续往右知道做过头，如此反复。就像是不断的坐车坐过站，然后坐车回去，并切换线路。
其实这个东西和 AVL 非常类似，很明显带有树的一些特性，或者说就是一个棵树，跳跃的过程其实就是类似二分查找的一个过程，每次的向下切换线路都会滤过一部分的节点。
插入
插入的过程会比搜索复杂一些，首先，最底层肯定的必定插入，接下来我们使用一个 50%概率的随机数比较，如果正面，提升，去往上一级，到了上一级继续投硬币，如果正面，再次提升，如此反复，如果上层链表还不存在，生成他。
要注意的是，每一层链表的起始点都必须是一个负无穷的数。这可以避免搜索从右上角开始的问题。
实现
自己也依靠公开课中的描述以及自己的理解实现了一个跳跃表,书里好像没这章节，所以走了不少弯路，如果你们发现错误的话还请纠正一下。实际用代码实现的时候还是有些复杂的。
class Node {
constructor(val) {
this.val = val
this.low = null
this.high = null
this.left = null
this.right = null
this.lr = null // left root 该节点的最左边 负无限节点
}
}
class SkipList {
constructor() {
this.root = new Node(-Infinity) // 初始化 一层最左边的负无限节点
}
insert(val) {
let x = this.root
let lr = this.root
let tmp = {} // 虚体 吃时候为了让while第一次跑起来
while (x !== null && tmp !== null) {
// 注意插入判断的顺序 首先判断 当前是否已经到了最后一个值 代表直接插入到最后
// 接下来就是普通的判断 前面比目标小 后面比目标大
if (x.right === null || (val >= x.val && val <= x.right.val)) {
let node = new Node(val)
// 在这一层的插入
node.right = x.right
x.right = node
node.left = x
node.lr = lr
if (tmp.val) {
// 如果tmp存在 并且是实体 互相链接
node.low = tmp
tmp.high = node
}
// 如果这个节点 属于是当前层级的最右节点，并且上层已经建立 无条件升级
// 或者 投硬币成功
if ((node.right === null && lr.high !== null) || Math.random() > 0.5) {
// tmp会被下一层用来连接
tmp = node
// 如果没有上层 去往left-root 建立一层
if (lr.high === null) {
lr.high = new Node(-Infinity)
lr.high.low = lr
}
x = lr.high
lr = lr.high
} else {
tmp = null
}
} else {
x = x.right
}
}
}
search(val) {
let x = this.root
// 首先找到左上角定点
while (x.high !== null) {
x = x.high
}
// 如果都为如果都为false就代表已经到了右下角的节点
while (x.right !== null || x.low !== null) {
if (x.val === val) {
return 'yes i find'
}
if (x.val > val) {
// 其实这时候已经可以返回false了 因为接下来x的val只可能越来越大
return 'no result'
}
// 要找节点还在右边 继续
if (x.right.val <= val) {
x = x.right
} else if (x.right.val > val) {
// 已经坐过头了 向下一层
x = x.low
}
}
return 'no result'
}
}
图片版
我只想说 太酷了 这些创造数据结构的人真是太帅了啊