Skiplist

起因, Leetcode 1206. 设计跳表, 愣是没通过题目给的动图看懂搜索过程, 遂学之

基本思想

看图! 同一个结点之间, 从高层至低层有连接.

查找, 插入, 删除的时间复杂度都是 $O(\log{n})$, 时间期望与红黑树一样, 不过跳表是有序链表的改进, 而非二叉树.

有序链表的查找时间复杂度显然 $O(n)$, 但跳表引入了分层. 最底层是初始有序链表, 定义位于第 $i$ 层的结点出现在第 $i+1$ 层的概率为 $p$(常数).

查找时, 从高到低层查找. 在每层逐个比较直至满足当前结点的下一结点大于等于目标值时, 进入下一层, 直至到第一层结束. 最终, 若下一结点值为目标值则查询成功, 反之元素不存在. 由于从高往低搜索, 所以会跳过一些无意义的比较, 最终能达到 $O(\log{n})$

获取结点最大层数

实现方法很简单, 随机数模拟概率, 成功则最大层数增加一层

mt19937 gen{random_device()};
// 默认输出[0, 1)均匀分布
uniform_real_distribution<double> dis;
int randomLevel()
{
    int cur = 1;
    while (dis(gen) < p && cur < maxlevel)
        ++cur;
    return cur;
}

查询

从高到低, 每一层向右搜寻, 直至当前层下一个结点值大于等于目标值. 最终的结点与下一结点的值满足: $cur.val < target \leq cur.next.val$

bool search(int target)
{
    auto cur = root;
    for (int level = maxlevel - 1; level >= 0; --level)
        while (cur->next[level] && cur->next[level]->val < target)
            cur = cur->next[level];
    cur = cur->next[0];
    if (cur && cur->val == target)
        return true;
    return false;
}

插入

由于需要知道每层要插入的地点, 因此其中包含查询过程. 每层都记录下待插入的结点, 最终通过随机数获取当前结点的最大层数 curLevel, 从存储的 $[0, curLevel]$ 结点后插入新结点.

void add(int target)
{
    vector<node *> update(maxlevel);
    auto cur = root;
    for (int level = maxlevel - 1; level >= 0; --level)
    {
        while (cur->next[level] && cur->next[level]->val < target)
            cur = cur->next[level];
        update[level] = cur;
    }
    int curLevel = randomLevel();
    node *insert = new node(target, maxlevel);
    for (int level = 0; level <= curLevel; ++level)
    {
        // update -> insert -> update.next
        insert->next[level] = update[level]->next[level];
        update[level]->next[level] = insert;
    }
}

删除

同理插入, 记录待删除结点的前一结点位置. 根据下一结点信息可以进行剪枝(若下一结点值非目标值, 则证明已经删完与目标值对应的结点, 可以提前退出循环)

bool erase(int target)
{
    vector<node *> update(maxlevel);
    auto cur = root;
    for (int level = maxlevel - 1; level >= 0; --level)
    {
        while (cur->next[level] && cur->next[level]->val < target)
            cur = cur->next[level];
        update[level] = cur;
    }
    cur = cur->next[0];
    if (!cur || cur->val != target)
        return false;
    for (int level = 0; level < maxlevel; ++level)
    {
        if (update[level]->next[level] != cur)
            break;
        update[level]->next[level] = cur->next[level];
    }
    delete cur;
    return true;
}

总结

这玩意儿, 第一次见到半小时内肯定写不出的阿. 光是思想就算不上简单了, 而且还是基于链表的, 指针操作等等细节也需要很注意. 写起来很麻烦. 下述代码可以通过前文提及的 Leetcode 题目.

class Skiplist
{
private:
    struct node
    {
        int val;
        vector<node *> next;
        node(const int V = -1, const int MAXLEVEL = 32) : val(V), next(MAXLEVEL, nullptr) {}
    };
    node *root;
    int maxlevel;
    double p;
    mt19937 gen{random_device{}()};
    uniform_real_distribution<double> dis;
    int randomLevel()
    {
        int cur = 0;
        while (dis(gen) < p && cur + 1 < maxlevel)
            ++cur;
        return cur;
    }

public:
    Skiplist(const int MAXLEVEL = 32, const double P = 0.25) : maxlevel(MAXLEVEL), p(P), root(new node()) {}

    bool search(int target)
    {
        auto cur = root;
        for (int level = maxlevel - 1; level >= 0; --level)
            while (cur->next[level] && cur->next[level]->val < target)
                cur = cur->next[level];
        cur = cur->next[0];
        if (cur && cur->val == target)
            return true;
        return false;
    }
    void add(int target)
    {
        vector<node *> update(maxlevel);
        auto cur = root;
        for (int level = maxlevel - 1; level >= 0; --level)
        {
            while (cur->next[level] && cur->next[level]->val < target)
                cur = cur->next[level];
            update[level] = cur;
        }
        int curLevel = randomLevel();
        node *insert = new node(target, maxlevel);
        for (int level = 0; level <= curLevel; ++level)
        {
            // update -> insert -> update.next
            insert->next[level] = update[level]->next[level];
            update[level]->next[level] = insert;
        }
    }
    bool erase(int target)
    {
        vector<node *> update(maxlevel);
        auto cur = root;
        for (int level = maxlevel - 1; level >= 0; --level)
        {
            while (cur->next[level] && cur->next[level]->val < target)
                cur = cur->next[level];
            update[level] = cur;
        }
        cur = cur->next[0];
        if (!cur || cur->val != target)
            return false;
        for (int level = 0; level < maxlevel; ++level)
        {
            if (update[level]->next[level] != cur)
                break;
            update[level]->next[level] = cur->next[level];
        }
        delete cur;
        return true;
    }
    ~Skiplist() { delete root; }
};