MIT算法导论公开课之第12课 跳跃表

动态搜索结构

跳跃表（skip list）
树堆（treap）
红黑树（red black tree）
B树（B tree）

跳跃表

一种简单、高效的动态搜索结构，使用了随机化算法。
插入删除操作的期望的运行时间为O(lgn)，并且这种情况有很高的概率（≈1-1/n^α）。

有序的链表

搜索一个排好序的链表所用时间为O(n)，因为链表不支持随机访问。

改进链表

使用两个有序的链表，以加快查询速度。

• Ex（纽约地铁第七大道线）：

  • 站号（快线和慢线）：
    14、23、34、42、50、59、66、72
    79、86、96、103、110、116、125
  • 结构示意图：
    
    L2存储所有的元素，L1存储某些子集元素，L1和L2中键值相同的元素之间有链接。

• 查询过程：

  • Search(x)：
    在顶层链表L1中从左向右遍历，直到走过头，后退一个结点，然后向下继续走下层链表L2直到x。

• 关于创建L1：
  最好均匀的选取结点作为L1中的结点。
  =>搜索时间≈|L1|+|L2|/|L1|（|L2|=n）
  最小化|L1|+n/|L1|：
  当|L1|=n/|L1|能得到最小值，此时|L1|=n^(1/2)，最小值为2·n^(1/2)。
  

• 一般化分析：
  使用2个有序的链表，运行时间为O(2·n^(1/2))。
  使用3个有序的链表，运行时间为O(3·n^(1/3))。
  使用k个有序的链表，运行时间为O(k·n^(1/k))。
  k选取为lgn时，运行时间为O(lgn·n^(1/lgn))=O(lgn·2^(lgn/lgn))=O(2lgn)。
  一共有lgn层，所有相邻两层比值的乘积应该等于n，即r^(lgn)=n=>r=2。
  相邻两层比值为2。
  

跳跃表

实现插入和删除，并能尽量好的维护这个结构，使搜索代价仍为O(lgn)。

• 跳跃表操作：

Insert(x)：
    确定x在底层链表中的位置，把x插入到此位置。
    确定是否将该元素提升到上一层：
        抛一枚硬币，正面就提升到上一层链表，并再抛一次硬币，反面就结束操作。
        注：为保证能从多层链表的左上角开始操作，将每一层开始结点值设为负无穷。
高度提升到lgn以上的概率为(1/2)^lgn=1/(2^lgn)=1/n。
算法对输入序列无要求，但这个数据结构执行速度快的高概率要求每次随机抛硬币。
delete(x)：
    在每一层中找到x，并删除。

• 跳跃表特性：