跳跃表（skiplist）

---

• 鸣谢：

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

总结一下步骤：

• 插入：

1. 通过索引指针圈定插入元素所在的范围，最后确定底层链表的插入位置。O（logN）
2. 利用抛硬币的随机方式，决定新节点是否提升为上一级索引。结果为“正”则提升并继续抛硬币，结果为“负”则停止。O（logN）
3. 注意：索引还有最底层的操作要分开，因为索引需要递归下降，而最底层不需要，删除的时候也是。

• 删除：

1. 自上而下，查找第一次出现节点的索引，并逐层找到每一层对应的节点。O（logN）
2. 删除每一层查找到的节点，通过插入时在头结点做的标记，如果删完后该层只剩下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