Skip List - 跳跃表
跳跃表
跳跃表是一种随机化链表数据结构，其添加、删除、查找的时间复杂度与平衡树/二叉查找树的时间复杂度相同。相比平衡树，跳跃表的实现方式更简单，实际应用中对并发的支持更好（内部多条链表可以分别由不同线程操作），但占更多内存。
跳跃表的每个节点可以包含多个指针，因为它们可以参与多个内部链表。下图是一个典型的跳跃表：
查找
在跳跃表中查找元素，要从最高层链表向下到最低层链表，更高一层链表充当了下一层链表的快速跑到。
从第一个节点的最高层链表开始，向右移动找到第一个节点满足或。若则查找结束；若或则退回上一个查找位置，然后移动到下一层链表，再递归的继续向右移动找到第一个满足或的节点。若直到最低层链表仍无法找到元素则说明该跳跃表中不存在该元素。
以上图中的跳跃表为例，查询元素的过程如下图所示：
查询过程中，在链表中经历了节点，在链表中经历了节点，在链表中经历了节点，在链表中经历了节点最终找到元素。
查询元素的过程如下图所示：
查询过程中，在链表中经历了节点，在链表中经历了节点，在链表中经历了节点，在链表中经历了节点最终无法找到元素。
插入
在跳跃表中插入元素，与查找操作基本一致，也是从最高层链表向下到最低层链表（最终节点一定要在最低层的原始链表中插入），找到合适的位置后插入新节点。最低层链表插入节点后，高层链表的节点数量不足导致时间复杂度退化。
跳跃表通过随机数来做一个“抛硬币”的操作，决定新节点是否应该提升到上一层链表中。若结果为“是”则一直将新节点提升，若结果为“否”则结束本次插入操作。一般将抛硬币得到“是”的概率设置为（或）。对于包含个节点，概率为的跳跃表，链表的高度为
实际实现中会指定一个最大高度，例如。
删除
在跳跃表中删除元素，首先查找在最低层的原始链表中的位置，将其删除，然后依次向上，将从所有上层链表中删除即可。