open-courses
Search…
Skip Lists

简介

Skip Lists 是一种随机数据结构(Randomized Data Structure),它是 Set (Ordered Set) 的一种实现。它的各操作复杂度如下表所示:
Operation Name
Time Complexity
Space Complexity
find-key(k)
O(lgn)O(lgn)
O(1)O(1)
iter()
O(n)O(n)
O(n)O(n)
insert(x)
O(lgn)O(lgn)
O(1)O(1)
delete-key(k)
O(lgn)O(lgn)
O(1)O(1)
delete-min/max()
O(lgn)O(lgn)
O(1)O(1)
find-next/prev(k)
O(lgn)O(lgn)
O(1)O(1)
find-min/max()
O(lgn)O(lgn)
O(1)O(1)
order-iter()
O(n)O(n)
O(1)O(1)

从 Find/Search 谈起

One Linked List

图 1 - One Linked List
当我们有一个 Linked List 时,Search 操作在最差情况下的复杂度为
θ(n)θ(n)
,我们有什么方式能够提高它的速度呢?

Two Linked Lists

快速公交系统(BRT)与普通公交系统的区别在于:普通公交系统与其它私人交通工具共享车道且每站必停,而快速公交系统独享车道,且只经停部分公交站。那么假如我要从 A 地区 B 地(快速公交不可直达),就可以先从 A 开始乘坐快速公交到达离 B 最近的公交站,再乘坐普通公交到达 B。如果我们把 Search 操作比喻成这样的乘车过程,可以考虑使用两个 Linked Lists:
图 2 - Two Linked Lists
如图 2 所示,举例如下:
14 -> 59:14 -> 34 -> 42 -> 50 -> 59 14 -> 79:14 -> 34 -> 42 -> 72 -> 79
怎么设计快速公交系统的停靠站能使得公交系统的性能达到最大?直觉告诉我们,将快速公交的停靠站平均分布在普通公交停靠站上。那么这时候 Search 的成本为:
searchcost=L1+L2L1searchcost = |L_1| + \frac{|L_2|}{|L_1|}
求其最小值,可以得到:
L12=L2=n=>L1=n|L1|^2 = |L2| = n => |L1| = \sqrt{n}
如此一来,Search 的成本就是:
L1+L2L1=n+nn=2n |L_1| + \frac{|L_2|}{|L_1|} = \sqrt{n} + \frac{n}{\sqrt{n}} = 2\sqrt{n}

More Linked Lists

Number Of Linked Lists
Search Cost
2
2n2\sqrt{n}
3
3n33\sqrt[3]{n}
4
4n44\sqrt[4]{n}
...
...
lgnlgn
lgnnlgn=2lgnlgn\sqrt[lgn]{n} = 2lgn
使用
lgnlgn
个 linked lists 时,已经很像一棵树,如 B 树。

Skip Lists

完美的 Skip Lists 就是由
lgnlgn
个 linked lists 构成的数据结构。

Insert(x)

从空的 Skp Lists 开始不断 Insert 元素,就构成了 Skip Lists 的创建过程。如何保证这个过程能够建立出接近完美的 Skip Lists 其实就是 Insert 的实现需要解决的问题。
方案:先用 search/find 找到元素在最底层的位置,将元素插入到最底层中,然后以 1/2 的概率决定是否将该元素插入到上面一层,递归重复。根据概率理论,平均来看 ---
  • 1/2 的元素会被插入到上面 0 层
  • 1/4 的元素会被插入到上面 1 层
  • 1/8 的元素会被插入到上面 2 层
  • ...(以此类推)
search 的时间复杂度为
O(lgn)O(lgn)
,递归插入的时间复杂度同样为
O(lgn)O(lgn)
,因此 insert 的总时间复杂度也为
O(lgn)O(lgn)

Delete(x)

Delete 需要先用 search/find 找到元素的位置,然后从所有可能存在该元素的链表中删除该元素,因此总时间复杂度为
O(lgn)O(lgn)
具体证明请查阅参考资料。

参考