【Leetcode】1206. Design Skiplist

题目地址：

https://leetcode.com/problems/design-skiplist/

实现一个跳表。

跳表如下图所示：

其是一个分层有序链表结构（有序指的是按元素大小排序，类似于平衡树），设最下层为第$0$层，向上的层数以此类推。每一层的节点数大致是其上面一层的两倍，而查找元素的时候可以通过高层的快速跳跃实现优化。有个虚拟头结点为搜索的出发节点。核心操作为“前驱查找”，这个操作会找到每一层的小于给定元素$x$的最后一个节点（如果不存在，则视为找到了头结点）。

每个操作具体如下：
1、查找$x$是否存在。先对$x$进行前驱查找，然后看第$0$层找到的那个节点的下一个节点，只需要看其是否值为$x$即可；
2、添加$x$。先对$x$进行前驱查找，然后看第$0$层找到的那个节点，如果那个节点存在，则其为小于$x$的最后一个节点；如果不存在，那个节点即为头结点。无论怎样，都可以在那个节点之后添加新的值为$x$的节点。此时，以$50\%$的概率将这个节点插到上一层，插完之后再以$50\%$的概率将这个节点插到更上一层，一直插到最上层或中间停止了为止。
3、删除$x$。先对$x$进行前驱查找，然后看第$0$层找到的那个节点，看其下一个节点，如果不存在，或者值不为$x$，则说明$x$不存在，直接返回。否则说明找到了，删除之，并向上爬，删除上面层中的$x$。

代码如下：

class Skiplist {
    
 public:
#define level 8
  struct Node {
    
    int val;
    vector<Node*> next;
    Node(int val) : val(val) {
    
      next.resize(level, nullptr);
    }
  } *head;

  Skiplist() {
    
    head = new Node(-1);
  }

  ~Skiplist() {
    
    delete head;
  }

  void find(int x, vector<Node*> &pre) {
    
    // 从头结点出发，找到每一层小于x的最后一个节点，如果没找到则赋为头结点
    auto p = head;
    for (int i = level - 1; i >= 0; i--) {
    
      while (p->next[i] && p->next[i]->val < x) p = p->next[i];
      pre[i] = p;
    }
  }

  bool search(int x) {
    
    vector<Node*> pre(level);
    find(x, pre);
    auto p = pre[0]->next[0];
    return p && p->val == x;
  }

  void add(int x) {
    
    vector<Node*> pre(level);
    find(x, pre);
    auto p = new Node(x);
    // 从下向上每一层添加节点x
    for (int i = 0; i < level; i++) {
    
      p->next[i] = pre[i]->next[i];
      pre[i]->next[i] = p;
      // 以50%的概率退出
      if (rand() & 1) break;
    }
  }

  bool erase(int x) {
    
    vector<Node*> pre(level);
    find(x, pre);
    auto p = pre[0]->next[0];
    if (!p || p->val != x) return false;
    for (int i = 0; i < level && pre[i]->next[i] == p; i++)
      pre[i]->next[i] = p->next[i];
    delete p;
    return true;
  }
};

每个操作平均时间复杂度$O(\log n)$，$n$为表里已有的元素个数（即最下面一层的节点个数），空间平均$O(n)$。