跳表

底层保存全部有序键，上层只保留其中一部分，使一次向右移动能够跨过多个底层节点。查找从高层开始，在不越过目标键的前提下向右前进，不能再前进时下降一层，逐步缩小需要细查的区间。

每个节点可以有不同数量的前向链接，对应它参与的层。到达最底层后，再按完整键比较确认是否找到目标；高层靠近某处，只是帮助定位，并不等于该键一定存在。

参考：[1]

一种典型规则从底层节点开始反复掷公平硬币，正面就提升一层，反面停止。于是更高层的预期节点数不断减少；无需每次插入后重排整串节点，强行保持每隔固定数量就有一个快捷节点。

在相应独立随机选择的模型下，跳表的查找、插入与删除具有O(log n)期望成本，整体存储期望为O(n)。这里的期望针对构造时的随机选择，而不是假定使用者恰好按有利顺序输入键；个别随机结果仍可能较差。

参考：[1] [2]

插入先查找新键，并记录各层它前面的节点，再按新节点的随机高度，把相应层的前向链接接入。删除也先定位并保存这些前驱，然后在节点参与的各层解除连接，而不只移除底层那一个位置。

跳表因而沿用链表式局部修改，却还要维护层数、边界哨兵与各层链接的一致性。它不通过旋转维持AVL或红黑不变量；随机期望保证、实际空间和极端单次延迟，需要与确定性平衡树的保证分别比较。

参考：[1]