Skip Lists 是一种随机数据结构(Randomized Data Structure),它是 Set (Ordered Set) 的一种实现。它的各操作复杂度如下表所示:
Operation Name
Time Complexity
Space Complexity
find-key(k)
O(lgn)
O(1)
iter()
O(n)
O(n)
insert(x)
O(lgn)
O(1)
delete-key(k)
O(lgn)
O(1)
delete-min/max()
O(lgn)
O(1)
find-next/prev(k)
O(lgn)
O(1)
find-min/max()
O(lgn)
O(1)
order-iter()
O(n)
O(1)
从 Find/Search 谈起
One Linked List
图 1 - One Linked List
当我们有一个 Linked List 时,Search 操作在最差情况下的复杂度为
θ(n)
,我们有什么方式能够提高它的速度呢?
Two Linked Lists
快速公交系统(BRT)与普通公交系统的区别在于:普通公交系统与其它私人交通工具共享车道且每站必停,而快速公交系统独享车道,且只经停部分公交站。那么假如我要从 A 地区 B 地(快速公交不可直达),就可以先从 A 开始乘坐快速公交到达离 B 最近的公交站,再乘坐普通公交到达 B。如果我们把 Search 操作比喻成这样的乘车过程,可以考虑使用两个 Linked Lists: