题目描述

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

跳表是在 $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)。

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

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

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

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

样例

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 <= 20000
• 最多调用 50000 次 search，add 以及 erase 操作。

算法

(数据结构)

1. 数据结构的增、删、查、改都可以归结为查找操作。
2. 定义节点结构体，其中包含值 val，和一个层级指针数组 suc，suc[i] 表示在第 i 层的后继节点。
3. 定义头节点作为哨兵，初始时，每一层的指针都指向空。
4. 为了方便，我们这里的查找定义为查找严格小于当前值且值最大的节点，且每一层都需要返回这样的一个节点。
5. 真正查找时，只需要判断最底层节点的后继节点的值是否等于待查询值。
6. 插入时，从最底层开始在当前节点的后侧新建节点插入，同时以 50% 的概率去更高层继续插入。
7. 删除时，判断最底层节点的后继节点的值是否等于待删除值，如果等于删除，然后去更高层继续删除。

C++ 代码

#define LEVEL 8

class Node {
public:
    int val;
    vector<Node*> suc;

    Node(int val_):val(val_) {
        suc.resize(LEVEL, NULL);
    }
};

class Skiplist {
private:
    Node *head;
public:
    Skiplist() {
        head = new Node(-1);
    }

    ~Skiplist() {
        delete head;
    }

    void findLess(int target, vector<Node*> &pre) {
        Node *p = head;
        for (int i = LEVEL - 1; i >= 0; i--) {
            while (p->suc[i] && p->suc[i]->val < target)
                p = p->suc[i];

            pre[i] = p;
        }
    }

    bool search(int target) {
        vector<Node*> pre(LEVEL);
        findLess(target, pre);

        Node *obj = pre[0]->suc[0];

        return obj && obj->val == target;
    }

    void add(int num) {
        vector<Node*> pre(LEVEL);
        findLess(num, pre);

        Node *obj = new Node(num);

        for (int i = 0; i < LEVEL; i++) {
            obj->suc[i] = pre[i]->suc[i];
            pre[i]->suc[i] = obj;
            if (rand() % 2 == 0)
                break;
        }
    }

    bool erase(int num) {
        vector<Node*> pre(LEVEL);
        findLess(num, pre);

        Node *obj = pre[0]->suc[0];

        if (!obj || obj->val > num)
            return false;

        for (int i = 0; i < LEVEL && pre[i]->suc[i] == obj; i++)
            pre[i]->suc[i] = obj->suc[i];

        delete obj;

        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);
 */