WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数据结构部分简介
栈
队列
链表
哈希表
并查集
堆简介
二叉堆
配对堆
左偏树
分块思想
块状数组
块状链表
树分块
Sqrt Tree
单调栈
单调队列
ST 表
树状数组
线段树
李超线段树
区间最值操作 & 区间历史最值
划分树
二叉搜索树简介
Treap
Splay
WBLT
Size Balanced Tree
AVL 树
替罪羊树
笛卡尔树
左偏红黑树
跳表
可持久化数据结构简介
可持久化线段树
可持久化块状数组
可持久化平衡树
可持久化字典树
可持久化可并堆
线段树套线段树
平衡树套线段树
线段树套平衡树
树状数组套主席树
分块套树状数组
K-D Tree
珂朵莉树
Link Cut Tree
Euler Tour Tree
Top Tree
析合树
50 objects
本站非官方,所收集资源均来源于网络。
跳表 - 数据结构
跳表(Skip List)是由 William Pugh 发明的一种查找数据结构,支持对数据的快速查找,插入和删除。 跳表的期望空间复杂度为 $O(n)$ ,跳表的查询,插入和删除操作的期望时间复杂度都为 $O(\log n)$ 。 ## 基本思想 顾名思义,跳表是一种类似于链表的数据结构。更加准确地说,跳表是对有序链表的改进。 为方便讨论,后续所有有序链表默认为 **升序** 排序。 一个有序链表的查找操作,就是从头部开始逐个比较,直到当前节点的值大于或者等于目标节点的值。很明显,这个操作的复杂度是 $O(n)$ 。 跳表在有序链表的基础上,引入了 **分层** 的概念。首先,跳表的每一层都是一个有序链表,特别地,最底层是初始的有序链表。每个位于第 $i$ 层的节点有 $p$ 的概率出现在第 $i+1$ 层, $p$ 为常数。 记在 n 个节点的跳表中,期望包含 $\frac{1}{p}$ 个元素的层为第 $L(n)$ 层,易得 $L(n) = \log_{\frac{1}{p}}n$ 。 在跳表中查找,就是从第 $L(n)$ 层开始,水平地逐个比较直至当前节点的下一个节点大于等于目标节点,然后移动至下一层。重复这个过程直至到达第一层且无法继续进行操作。此时,若下一个节点是目标节点,则成功查找;反之,则元素不存在。这样一来,查找的过程中会跳过一些没有必要的比较,所以相比于有序链表的查询,跳表的查询更快。可以证明,跳表查询的平均复杂度为 $O(\log n)$ 。 ## 复杂度证明 ### 空间复杂度 对于一个节点而言,节点的最高层数为 $i$ 的概率为 $p^{i-1}(1 - p)$ 。所以,跳表的期望层数为 $\sum_{i>=1} ip^{i - 1}(1-p) = \frac{1}{1 - p}$ ,且因为 $p$ 为常数,所以跳表的 **期望空间复杂度** 为 $O(n)$ 。 在最坏的情况下,每一层有序链表等于初始有序链表,即跳表的 **最差空间复杂度** 为 $O(n \log n)$ 。 ### 时间复杂度 从后向前分析查找路径,这个过程可以分为从最底层爬到第 $L(n)$ 层和后续操作两个部分。在分析时,假设一个节点的具体信息在它被访问之前是未知的。 假设当前我们处于一个第 $i$ 层的节点 $x$ ,我们并不知道 $x$ 的最大层数和 $x$ 左侧节点的最大层数,只知道 $x$ 的最大层数至少为 $i$ 。如果 $x$ 的最大层数大于 $i$ ,那么下一步应该是向上走,这种情况的概率为 $p$ ;如果 $x$ 的最大层数等于 $i$ ,那么下一步应该是向左走,这种情况概率为 $1-p$ 。 令 $C(i)$ 为在一个无限长度的跳表中向上爬 $i$ 层的期望代价,那么有: $$ \begin{aligned} C(0) & = 0 \\\\ C(i) & = (1-p)(1+C(i)) + p(1+C(i-1)) \end{aligned} $$ 解得 $C(i)=\frac{i}{p}$ 。 由此可以得出:在长度为 $n$ 的跳表中,从最底层爬到第 $L(n)$ 层的期望步数存在上界 $\frac{L(n) - 1}{p}$ 。 现在只需要分析爬到第 $L(n)$ 层后还要再走多少步。易得,到了第 $L(n)$ 层后,向左走的步数不会超过第 $L(n)$ 层及更高层的节点数总和,而这个总和的期望为 $\frac{1}{p}$ 。所以到了第 $L(n)$ 层后向左走的期望步数存在上界 $\frac{1}{p}$ 。同理,到了第 $L(n)$ 层后向上走的期望步数存在上界 $\frac{1}{p}$ 。 所以,跳表查询的期望查找步数为 $\frac{L(n) - 1}{p} + \frac{2}{p}$ ,又因为 $L(n)=\log_{\frac{1}{p}}n$ ,所以跳表查询的 **期望时间复杂度** 为 $O(\log n)$ 。 在最坏的情况下,每一层有序链表等于初始有序链表,查找过程相当于对最高层的有序链表进行查询,即跳表查询操作的 **最差时间复杂度** 为 $O(n)$ 。 插入操作和删除操作就是进行一遍查询的过程,途中记录需要修改的节点,最后完成修改。易得每一层至多只需要修改一个节点,又因为跳表期望层数为 $\log_{\frac{1}{p}}n$ ,所以插入和修改的 **期望时间复杂度** 也为 $O(\log n)$ 。 ## 具体实现 ### 获取节点的最大层数 模拟以 $p$ 的概率往上加一层,最后和上限值取最小。 ```cpp int randomLevel() { int lv = 1; // MAXL = 32, S = 0xFFFF, PS = S * P, P = 1 / 4 while ((rand() & S) < PS) ++lv; return min(MAXL, lv); } ``` ### 查询 查询跳表中是否存在键值为 $key$ 的节点。具体实现时,可以设置两个哨兵节点以减少边界条件的讨论。 ```cpp V& find(const K& key) { SkipListNode
* p = head; // 找到该层最后一个键值小于key的节点,然后走向下一层 for (int i = level; i >= 0; --i) { while (p->forward[i]->key < key) { p = p->forward[i]; } } // 现在是小于,所以还需要再往后走一步 p = p->forward[0]; // 成功找到节点 if (p->key == key) return p->value; // 节点不存在,返回INVALID return tail->value; } ``` ### 插入 插入节点 $(key, value)$ 。插入节点的过程就是先执行一遍查询的过程,中途记录新节点是要插入哪一些节点的后面,最后再执行插入。每一层最后一个键值小于 $key$ 的节点,就是需要进行修改的节点。 ```cpp void insert(const K &key, const V &value) { // 用于记录需要修改的节点 SkipListNode
*update[MAXL + 1]; SkipListNode
*p = head; for (int i = level; i >= 0; --i) { while (p->forward[i]->key < key) { p = p->forward[i]; } // 第i层需要修改的节点为p update[i] = p; } p = p->forward[0]; // 若已存在则修改 if (p->key == key) { p->value = value; return; } // 获取新节点的最大层数 int lv = randomLevel(); if (lv > level) { lv = ++level; update[lv] = head; } // 新建节点 SkipListNode
*newNode = new SkipListNode
(key, value, lv); // 在第0-lv层插入新节点 for (int i = lv; i >= 0; --i) { p = update[i]; newNode->forward[i] = p->forward[i]; p->forward[i] = newNode; } ++length; } ``` ### 删除 删除键为 $key$ 的节点。删除节点的过程就是先执行一遍查询的过程,中途记录要删的节点是在哪一些节点的后面,最后再执行删除。每一层最后一个键值小于 $key$ 的节点,就是需要进行修改的节点。 ```cpp bool erase(const K &key) { // 用于记录需要修改的节点 SkipListNode
*update[MAXL + 1]; SkipListNode
*p = head; for (int i = level; i >= 0; --i) { while (p->forward[i]->key < key) { p = p->forward[i]; } // 第i层需要修改的节点为p update[i] = p; } p = p->forward[0]; // 节点不存在 if (p->key != key) return false; // 从最底层开始删除 for (int i = 0; i <= level; ++i) { // 如果这层没有p删除就完成了 if (update[i]->forward[i] != p) { break; } // 断开p的连接 update[i]->forward[i] = p->forward[i]; } // 回收空间 delete p; // 删除节点可能会是最大层数减少 while (level > 0 && head->forward[level] == tail) --level; // 跳表长度 --length; return true; } ``` ### 完整代码 下列代码是用跳表实现的 map。未经正经测试,仅供参考。 ### "参考代码" ```cpp #include
using namespace std; template
struct SkipListNode { int level; K key; V value; SkipListNode **forward; SkipListNode() {} SkipListNode(K k, V v, int l, SkipListNode *nxt = NULL) { key = k; value = v; level = l; forward = new SkipListNode *[l + 1]; for (int i = 0; i <= l; ++i) forward[i] = nxt; } ~SkipListNode() { if (forward != NULL) delete[] forward; } }; template
struct SkipList { static const int MAXL = 32; static const int P = 4; static const int S = 0xFFFF; static const int PS = S / P; static const int INVALID = INT_MAX; SkipListNode
*head, *tail; int length; int level; SkipList() { srand(time(0)); level = length = 0; tail = new SkipListNode
(INVALID, 0, 0); head = new SkipListNode
(INVALID, 0, MAXL, tail); } ~SkipList() { delete head; delete tail; } int randomLevel() { int lv = 1; while ((rand() & S) < PS) ++lv; return min(MAXL, lv); } void insert(const K &key, const V &value) { SkipListNode
*update[MAXL + 1]; SkipListNode
*p = head; for (int i = level; i >= 0; --i) { while (p->forward[i]->key < key) { p = p->forward[i]; } update[i] = p; } p = p->forward[0]; if (p->key == key) { p->value = value; return; } int lv = randomLevel(); if (lv > level) { lv = ++level; update[lv] = head; } SkipListNode
*newNode = new SkipListNode
(key, value, lv); for (int i = lv; i >= 0; --i) { p = update[i]; newNode->forward[i] = p->forward[i]; p->forward[i] = newNode; } ++length; } bool erase(const K &key) { SkipListNode
*update[MAXL + 1]; SkipListNode
*p = head; for (int i = level; i >= 0; --i) { while (p->forward[i]->key < key) { p = p->forward[i]; } update[i] = p; } p = p->forward[0]; if (p->key != key) return false; for (int i = 0; i <= level; ++i) { if (update[i]->forward[i] != p) { break; } update[i]->forward[i] = p->forward[i]; } delete p; while (level > 0 && head->forward[level] == tail) --level; --length; return true; } V &operator[](const K &key) { V v = find(key); if (v == tail->value) insert(key, 0); return find(key); } V &find(const K &key) { SkipListNode
*p = head; for (int i = level; i >= 0; --i) { while (p->forward[i]->key < key) { p = p->forward[i]; } } p = p->forward[0]; if (p->key == key) return p->value; return tail->value; } bool count(const K &key) { return find(key) != tail->value; } }; int main() { SkipList
L; map
M; clock_t s = clock(); for (int i = 0; i < 1e5; ++i) { int key = rand(), value = rand(); L[key] = value; M[key] = value; } for (int i = 0; i < 1e5; ++i) { int key = rand(); if (i & 1) { L.erase(key); M.erase(key); } else { int r1 = L.count(key) ? L[key] : 0; int r2 = M.count(key) ? M[key] : 0; assert(r1 == r2); } } clock_t e = clock(); cout << "time elapse: " << (double)(e - s) / CLOCKS_PER_SEC << endl; // about 0.2s return 0; } ``` ## 跳表的随机访问优化 访问跳表中第 $k$ 个节点,相当于访问初始有序链表中的第 $k$ 个节点,很明显这个操作的时间复杂度是 $O(n)$ 的,并不足够优秀。 跳表的随机访问优化就是对每一个前向指针,再多维护这个前向指针的长度。假设 $A$ 和 $B$ 都是跳表中的节点,其中 $A$ 为跳表的第 $a$ 个节点, $B$ 为跳表的第 $b$ 个节点 $(a < b)$ ,且在跳表的某一层中 $A$ 的前向指针指向 $B$ ,那么这个前向指针的长度为 $b - a$ 。 现在访问跳表中的第 $k$ 个节点,就可以从顶层开始,水平地遍历该层的链表,直到当前节点的位置加上当前节点在该层的前向指针长度大于等于 $k$ ,然后移动至下一层。重复这个过程直至到达第一层且无法继续行操作。此时,当前节点就是跳表中第 $k$ 个节点。 这样,就可以快速地访问到跳表的第 $k$ 个元素。可以证明,这个操作的时间复杂度为 $O(\log n)$ 。 ## 参考资料 1. [Skip Lists: A Probabilistic Alternative to Balanced Trees](https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/pugh-skiplists-cacm1990.pdf) 2. [Skip List](https://en.wikipedia.org/wiki/Skip_list) 3. [A Skip List Cookbook](http://cglab.ca/~morin/teaching/5408/refs/p90b.pdf)