跳跃表

跳跃表是一种有序链表，其中的每个节点包含数量可变的链接，并且节点中的第i个链接单独实现链表，它跳过少于i个链接的节点。

跳跃表支持平均O(lgN)，最坏O(N)的时间复杂度。大部分情况下，跳跃表的性能可以和平衡树相媲美，又因为跳跃表的实现比平衡树简单，所以很多程序使用跳跃表来代替平衡树。

技术要点

插入节点时，首要任务是确定该节点有多少个链接。确定方法: 每$t^{j}$个节点中一个至少有j+1个链接。

跳跃表层数的期望值约为$log^{N}_{t}$。

实现时可以使用以1/$t^{j}$为概率返回j+1的函数来随机化节点的层数。