医疗网站建设资讯,用DW做的网站生成链接,网站识别手机电脑代码,信息类网站介绍
跳表是一个能在 O ( n l o g n ) O(nlogn) O(nlogn)时间完成查找、插入、删除的数据结构#xff0c;相比于树形结构优点就是很好写#xff08;所以也用于实现Redis ZSet#xff09;。其核心思想就是维护一个元素有序的#xff0c;能随机提升索引层数的链表。最下面一…介绍
跳表是一个能在 O ( n l o g n ) O(nlogn) O(nlogn)时间完成查找、插入、删除的数据结构相比于树形结构优点就是很好写所以也用于实现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);*/
