【数据结构学习笔记】19：跳表（Skip List）

介绍

跳表是一个能在 $O (n l o g n)$ 时间完成查找、插入、删除的数据结构，相比于树形结构优点就是很好写（所以也用于实现Redis ZSet）。其核心思想就是维护一个元素有序的，能随机提升索引层数的链表。最下面一层就是一个普通的链表，存了所有的元素，而每次提升索引高度都一定会从最下面一层开始提升连续的若干层，因此从最上面的层到最下面的层，索引一定是从稀疏到稠密，所以在查询的时候就能从上层开始，很快的跳过一些元素，再向下一层走，逐渐定位到元素的位置。

实现思路

结构

固定跳表层数后，跳表的每个结点（存某个元素）都在每一层有一个next指针，指向这一层的下一个结点。

为了查询方便，设定一个虚拟头结点，这个虚拟头节点作为查询的起始节点，每一层会指向实际的这一层的起始节点。

内部操作：`find`

引入一个特殊的内部操作，用于定位结点在每一层的位置，不管是接下来要删除这个结点，还是在这个结点附近（前或者后）插入一个元素结点都能借用这个操作方便的找到它。

考虑到每一层都是一个单向链表，所以find操作一定是返回目标结点在每一层的前置结点。

因为这个操作希望得到的是一个Node指针的数组，这个数组会在下一步的操作（插入/删除/查询）中被用到，所以可以给这个跳表引入一个prev数组缓存这个信息，每次使用前直接清空就可以了。

查询操作：`search`

先find得到目标元素的prev数组，然后就能找到最下面那层的结点，即prev[0]->next[0]，根据结点是否存在以及是否是要找的元素就可以得到search的结果了。

添加操作：`add`

因为跳表是有序的，所以一定会按序添加到指定的位置上。先先find得到目标元素的prev数组，然后从最下层开始向上，除了最下面那层一定要插入，上面的层i如果（连续且随机地）需要派生这层的索引，就根据prev[i]是该节点在第i层的前置结点，在此层按照链表的方式插入这个索引就可以了。

删除操作：`erase`

先做一遍serach操作，确认要删除的元素存在，且构造好了prev数组，接下来从下层向上，对于每一层i，按照链表的方式判断要删除的结点在此层存在索引，就将索引删除。因为索引从下到上是连续存在的，所以删到找不到索引就一定已经删干净了，最后记得回收结点即可。

例题：LeetCode 1206. 设计跳表

class Skiplist {
private:static const int MAX_LEVEL = 8;struct Node {int val;Node** next;Node(int _val) :val(_val) {next = new Node*[MAX_LEVEL];memset(next, NULL, sizeof(Node*) * MAX_LEVEL);}} *head, **prev;void find(int target, Node** prev) {Node* p = head;for (int i = MAX_LEVEL - 1; i >= 0 ; i -- ) {while (p->next[i] && p->next[i]->val < target) p = p->next[i];prev[i] = p;}}public:Skiplist() {this->head = new Node(-1);this->prev = new Node*[MAX_LEVEL];}~Skiplist() {delete this->head;delete[] this->prev;}bool search(int target) {memset(prev, NULL, sizeof(Node*) * MAX_LEVEL);find(target, prev);auto p = prev[0]->next[0];return p && p->val == target;}void add(int num) {memset(prev, NULL, sizeof(Node*) * MAX_LEVEL);find(num, prev);auto p = new Node(num);for (int i = 0; i < MAX_LEVEL; i ++ ) {p->next[i] = prev[i]->next[i];prev[i]->next[i] = p;if (rand() % 2) break;}}bool erase(int num) {memset(prev, NULL, sizeof(Node*) * MAX_LEVEL);find(num, prev);auto p = prev[0]->next[0];if (!p || p->val != num) return false;for (int i = 0; i < MAX_LEVEL && prev[i]->next[i] == p; i ++ )prev[i]->next[i] = p->next[i];delete p;return true;}
};/*** Your Skiplist object will be instantiated and called as such:* Skiplist* obj = new Skiplist();* bool param_1 = obj->search(target);* obj->add(num);* bool param_3 = obj->erase(num);*/