跳跃表（skiplist）
2019-01-04 本文已影响45人
小幸运Q
- 鸣谢：
https://blog.csdn.net/xiaolei1982/article/details/50721877
https://zhuanlan.zhihu.com/p/53975333?utm_source=qq&utm_medium=social&utm_oi=636829908081446912
用空间换时间：
对于一个需要频繁插入删除的线性有序结构，如何使插入/删除的速度提升？
- 对于单向链表，无法使用二分查找无法降低复杂度，只能从头到脚遍历O(n)
- 对于数组，删除插入复杂度太高，O(n)
- 其实平衡二叉树挺好的，但是节点平衡操作的开销很大，如果插入删除频繁性能会受限。
- 上红黑树的话，性能差不多，但是如果需要多进程同时访问修改的话，红黑树有个平衡的过程，牵涉到大量的节点，争锁的代价也就相对较高了。
跳表：时间复杂度 O(log2(n))
加入多层索引加快访问速度：
image.png
如果有n个元素，因为是2分，所以层数就应该是上面的log2(n)层再加上自身的1层。
插入过程：
-
插入元素时生成一个随机数（0,1）决定是否插入第一层索引：
-
如果是1，则插入第一层索引，否则不插；随后不断重复该操作，直到第N层索引才停止：
注意：插入过程需要利用上层索引找到插入位置。
image.png
删除过程：
将该元素及其位于上层的相同元素顺蔓摸瓜全部删除。（具体操作是利用索引指针圈定范围然后由上而下逐个删除）
image.png
总结一下步骤：
- 插入：
- 通过索引指针圈定插入元素所在的范围，最后确定底层链表的插入位置。O（logN）
- 利用抛硬币的随机方式，决定新节点是否提升为上一级索引。结果为“正”则提升并继续抛硬币，结果为“负”则停止。O（logN）
- 注意：索引还有最底层的操作要分开，因为索引需要递归下降，而最底层不需要，删除的时候也是。
- 删除：
- 自上而下，查找第一次出现节点的索引，并逐层找到每一层对应的节点。O（logN）
- 删除每一层查找到的节点，通过插入时在头结点做的标记，如果删完后该层只剩下1个节点，则删除一整层（原链表除外）。O（logN）
如果出现重复的元素要插入的话怎么办？
上层索引不需要变，但是最底层数据层节点的*underline可以用于存储拥有相同元素值的数据链。当然为了偷懒我在代码里面没写有关数据重复的处理。
示例代码：
-
要注意删除还有插入的时候最底层节点不需要下沉
-
v.size()会变，不能放在删除处理的循环里面。
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define N 1000
// 使用带头结点的链表，本示例中不考虑重复元素插入删除的情况。
typedef struct Node{
int num;
// 每层的首元素对应的num用于计算行的长度，其他层用于存放数据
Node*next;
Node*underline;
Node(){
next=NULL;
num=0;
underline=NULL;
}
}Node;
// 按照从小到大插入一行。确定插入位置需要上层索引指引。
// 刚好命中上层元素(m<num<n)，
// 沿着m从上到下逐个收缩（每次需要两个指针一前一后这样好回退）
Node* addline(vector<Node*>&v,int line,int num){
int i=0;
v[line]->num++;
// 该行的长度++
Node*t=new Node();
t->num=num;
int linenow=v.size()-1;
// 当前所在行
// 初始化两个delete指针
Node*p=v[linenow];
Node*q=p->next;
// 自顶向下到对应 line的上一层节点
for(;linenow>line;linenow--){
while(q!=NULL){
if(q->num>num){
break;
}
q=q->next;
p=p->next;
}
p=p->underline;
q=p->next;
}
// line层不需要下沉(p=p->underline)
while(q!=NULL){
if(q->num>num){
break;
}
q=q->next;
p=p->next;
}
// 将点插入p,q两个指针之中
t->next=q;
p->next=t;
return t;
}
// 添加插入的元素到最底层，然后再从下往上逐层按概率添加。
void add(vector<Node*>&v,int num){
// topline指向上一层插入的num节点，nextline指向下一层插入的num节点，方便上下连接。
Node* topline;
Node* underline;
// 最底层必加，但是最底层不是索引不需要随机数判断。
underline=addline(v,0,num);
int height=1;
// 标记插入的行数
// srand必须放在函数外面，最好放在main函数里面。
while(rand()%2==1){
if(height<v.size()){
topline=addline(v,height,num);
topline->underline=underline;
underline=topline;
}
else{
// 超过表长,添加头节点
Node* t=new Node();
t->underline=v[v.size()-1];
v.push_back(t);
// 添加元素
Node *node=addline(v,height,num);
topline=node;
topline->underline=underline;
underline=topline;
}
height++;
}
}
// 依层打印
void print(vector<Node*>v){
int i;
cout<<"v has level: "<<v.size()-1<<endl;
for(i=0;i<v.size();i++){
cout<<"No."<<i<<" level: ";
Node*p=v[i]->next;
while(p!=NULL){
cout<<p->num<<" ";
p=p->next;
}
cout<<endl;
}
}
// 删除用它的underline指针
void del(vector<Node*>&v,int num){
int i,j;
int linenow=v.size()-1;
Node*p;
Node*q;
while(linenow>=0){
p=v[linenow];
q=p->next;
while(q!=NULL){
if(q->num==num){
// 元素数小于等于2了整行删除
if(v[linenow]->num<=2){
p=p->underline;
q=p->next;
int sz=v.size();
// v.size()在pop的时候会变化，所以要先缓存着
for(i=0;i<sz-linenow;i++)
{
// 如果上面有小于1的顶，那么也得一块删除。要不然只删除中间行的操作会很繁琐。
v.pop_back();
}
break;
}
// 正常删除
p->next=q->next;
free(q);
// 如果不是最底层不需要下沉
if(linenow>0){
p=p->underline;
q=p->next;
}
break;
}
else if(q->num>num){
p=p->underline;
q=p->next;
break;
}
else{
p=p->next;
q=q->next;
}
}
linenow--;
}
}
int main(){
int i,j;
vector<Node*>v;
Node *node=new Node();
v.push_back(node);
srand((unsigned)time(NULL));
add(v,4);
add(v,2);
add(v,3);
add(v,1);
add(v,6);
add(v,5);
print(v);
// 输入要删除的元素
cin>>i;
del(v,i);
print(v);
}
image.png
