「这是我参与2022首次更文挑战的第32天，活动详情查看：2022首次更文挑战」。

跳跃表特点

1、按照 score 来排序，如果 score 相等，那么则按照 ele 来排序。

2、平均查询时间复杂度 O(logn)。

跳跃表实现

跳跃表是由 server.h/zskiplistNode 和 server.h/zskiplist 两个结构定义其中

zskiplistNode 结构用于订阅跳跃表的节点，而 zskiplist 结构用于保存跳跃表相关的信息，比如节点的数量，以及想表头节点和表尾节点的指针等

跳跃表实现 server.h/zskiplistNode 结构定义：

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    //数据
    sds ele;
    //分值
    double score;
    //后退指针
    struct zskiplistNode *backward;
    //层
    struct zskiplistLevel {
        //前进指针
        struct zskiplistNode *forward;
        //跨度
        unsigned long span;
    } level[];
} zskiplistNode;
​

zskiplist 结构定义如下：

typedef struct zskiplist {
    //头节点和尾节点
    struct zskiplistNode *header, *tail;
    //表中节点的数量
    unsigned long length;
    //表中层数最大的节点层数
    int level;
} zskiplist;

以 zskiplist 为基础的数据结构图如下：

运用场景

• 跳跃表是有序集合（zset）的底层实现之一

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

设计跳表

力扣题目（1206）:

不使用任何库函数，设计一个 跳表 。

跳表 是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。

例如，一个跳表包含 [30, 40, 50, 60, 70, 90] ，然后增加 80、45 到跳表中，以下图的方式操作：

Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons

跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n))，空间复杂度是 O(n)。

了解更多 : https://en.wikipedia.org/wiki/Skip_list

在本题中，你的设计应该要包含这些函数：

• bool search(int target) : 返回target是否存在于跳表中。
• void add(int num): 插入一个元素到跳表。
• bool erase(int num): 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可。

注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。

示例 1:

输入
["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"]
[[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
输出
[null, null, null, null, false, null, true, false, true, false]

解释
Skiplist skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0);   // 返回 false
skiplist.add(4);
skiplist.search(1);   // 返回 true
skiplist.erase(0);    // 返回 false，0 不在跳表中
skiplist.erase(1);    // 返回 true
skiplist.search(1);   // 返回 false，1 已被擦除

提示:

• 0 <= num, target <= 2 * 104
• 调用search,add, erase 操作次数不大于 5 * 104

解题代码

下面是参考 redis 的 skiplist 的实现。代码如下：

public class Skiplist {
    private static final float SKIPLIST_P = 0.5f;
    private static final int MAX_LEVEL = 16;
    
    // 头节点
    Node head;

    // 节点对象
    class Node {
        int val;
        Node bw;   // 后退指针
        Node[] fw; // 前进指针
​
        // 构造函数
        public Node(int val) {
            this.val = val;
            fw = new Node[randomLevel()];
        }
​
        public Node(int val, int size) {
            this.val = val;
            fw = new Node[size + 1];
        }

        // 生成随机 level
        public int randomLevel() {
            int level = 1;
            while (Math.random() < SKIPLIST_P && level < MAX_LEVEL) {
                level++;
            }
            return level;
        }
    }
​
    // 生成默认的头节点
    public Skiplist() {
        head = new Node(-1, MAX_LEVEL);
    }

    // 查询
    public boolean search(int target) {
        Node p = searchNode(target);
        boolean b = p.val == target;
        //System.out.println(b);
        return b;
    }
    
    // 添加
    public void add(int num) {
        Node p = searchNode(num);
        Node n = new Node(num);
        n.bw = p;
        for (int i = 0; i < n.fw.length; i++) {
            Node f = p;
            while (f.bw != null && f.fw.length < i + 1) {
                f = f.bw;
            }
            if (i == 0 && f.fw[i] != null) {
                f.fw[i].bw = n;
            }
            n.fw[i] = f.fw[i];
            f.fw[i] = n;
        }
    }
    
    // 移除
    public boolean erase(int num) {
        if (isEmpty()) {
            //System.out.println(false);
            return false;
        }
        Node p = searchNode(num);
        if (p.val != num) {
            //System.out.println(false);
            return false;
        }
        for (int i = 0; i < p.fw.length; i++) {
            Node f = p.bw;
            while (f.bw != null && f.fw.length < i + 1) {
                f = f.bw;
            }
            if (i == 0 && f.fw[i].fw[i] != null) {
                f.fw[i].fw[i].bw = f;
            }
            f.fw[i] = f.fw[i].fw[i];
        }
        //System.out.println(true);
        return true;
    }
    
    // 查询节点
    private Node searchNode(int target) {
        if (isEmpty()) {
            return head;
        }
        Node p = head;
        for (int i = MAX_LEVEL; i >= 0; i--) {
            while (p.fw[i] != null && p.fw[i].val <= target) {
                p = p.fw[i];
            }
        }
        return p;
    }
    
    // 是否为空
    private boolean isEmpty() {
        return head.fw[0] == null;
    }
}

执行示例（执行结果）：