Skip List
构造
- 给定一个有序的链表。
- 选择连表中最大和最小的元素，然后从其他元素中按照一定算法（随机）随即选出一些元素，将这些元素组成有序链表。
- 为刚选出的每个元素添加指针指向下一层中值同自己相等的元素。Top指针指向该层首元素
- 重复2、3步，直到不再能选择出除最大最小元素以外的元素。
查找
- 从最上层的链（Sh）的开头开始
- 假设当前位置为p，它向右指向的节点为q（p与q不一定相邻），且q的值为y。将y与x作比较 (1) $x=y$ 输出查询成功及相关信息 (2) $x>y$ 从p向右移动到q的位置 (3) $x<y$ 从p向下移动一格
- 如果当前位置在最底层的链中（S0），且还要往下移动的话，则输出查询失败
插入
$r \rightarrow random()$
if $r<p$ then do A
else do B
初始时列高为1。插入元素时，不停地执行随机决策模块。如果要求执行的是A操作，则将列的高度加1，并且继续反复执行随机决策模块。直到第i次，模块要求执行的是B操作，我们结束决策，并向跳跃表中插入一个高度为i的列。
删除
- 在跳跃表中查找到这个元素的位置，如果未找到，则退出
- 将该元素所在整列从表中删除
- 将多余的“空链”删除