首页 > 其他分享 >手把手教你实现跳表！

手把手教你实现跳表！

时间：2023-09-28 09:44:04浏览次数：41  
标签：key nxt cur level 实现 手把手 跳表 lev 指针

发布于我的博客，也许同步更新于博客园

引入

跳表（跳跃表）能够维护一个数的集合（作用类似普通平衡树），查找时间复杂度为 \(\log n\)，与平衡树一样基于链表结构。由于不需要平衡树那么多旋转什么的，所以效率比较高，一般认为性能能打红黑树。除此以外，链表的特性使它能够以线性时间遍历某个子段。Redis 的有序集合就是用跳表实现的。

更简单来说，跳表是一个支持 \(\Theta(\log n)\) 时间随机访问的链表

定义

上面这个东西叫链表。

我们知道，链表只支持线性时间访问，所以不能二分。我们如果想维护一个有序序列的话，虽然插入删除很快，但是找到一个值对应的位置很慢。

我们又知道，链表的访问形式实际上是一个一个遍历，而它有 \(n\) 个元素，这是它 \(\Theta(n)\) 复杂度随机访问的根源所在。

那我们是不是可以给链表精简一下呢？比如说，我给链表多加几层，每层减少一半的元素，像这样：

（蓝色方框括起来的是一个节点，实现的时候我们不需要把上面几层显式地建出来，只需要创建对应层的指针即可。）

这样的话，我就能像上图这样找到 \(78\) 这个节点了。

橙色路径是原有路径，走了 \(4\) 次。而上面的绿色路径只走了 \(\log_2 4 = 2\) 个次。好好好，那我这样建的话，我就能在链表上二分了！
实际上这个东西叫完美跳表。

跳表分两种，一种是上面的完美跳表（暂且这样叫）。这个东西最大的特点就是过于理想化了。如果加上插入删除的话，维护对应层的指针就太难了，每次都得更新。

另一种是基于随机化的跳表。
要随机化的东西叫做 \(level\)。一个跳表节点的 \(level\)，代表着这个节点同时存在于 \(1 \sim level\) 层的链表中。比如说，上图的值为 \(1\) 的节点 \(level = 3\)，值为 \(23\) 的节点 \(level = 1\)。
取 \(level\) 的方式类似于抛硬币，计算 \(level\) 时，如果硬币正面朝上，就 \(+1\) 并继续抛；如果反面朝上，则停止。通过这样定下节点 \(level\) 的跳表就是我们今天要实现的跳表。

基本实现

为了方便演示，这里就不再封装跳表了，其实跟着教程一边走一边封装也是可行的。

一些变量

int level 记录跳表的最高 level。

Node head 为了防止过多的边界的分类讨论，建立一个空结点当头节点。

节点

动态分配内存太慢了，如果用动态分配的，我还不如直接 STL。

所以开好数组作为预分配的空间，然后我们可以开一个指针记录分配到了哪一个位置。需要创建新节点的时候直接返回一个 ++tot 即可。

struct Node {
    int key, level;
    Node* nxt[MAX_LEVEL];
} space[N], *tot = space;

此处 level 的含义是：该节点存在于 0 到 level - 1 层的链表中，与前文定义 1 到 level 不同。

垃圾回收可以自己实现，待会的整体演示里面会放。

分配一个新节点空间，返回新节点的指针：

#define new_node() (++tot)

创建一个值为 key 高度为 level 的节点：

Node* create_node(int level, int key) {
    Node* res = new_node();
    res->level = level;
    res->key = key;
    return res;
}

随机生成 level

前面说了，是抛硬币。

所以我们可以直接借用一些随机数生成器。

然后我们肯定不能让层数无限大啊，所以需要设置一个 MAX_LEVEL 作为最大层数。

#define MAX_LEVEL 12

std::random_device seed;
std::minstd_rand rng(seed());

int random_level() {
    int res = 1;
    while (res < MAX_LEVEL && (rng() & 1)) {
        ++res;
    }
    return res;
}

本人做了测试，在随机种子 + 1000 次取值的测试下，梅森缠绕和线性同余两种算法通过 & 1 求出来的平均值基本上就是 \(0.5\pm 0.03\)，而且线性同余性能远比梅森缠绕高。然后用 PCG 算法测试了一下，发现 PCG 官方给的 C++ 实现能够做到 \(0.5\pm 0.02\)，性能接近线性同余，但是这玩意考场上得自己实现，所以还是用线性同余吧。

插入节点

声明：

void insert(int key);

三步走：找到需要插入的位置，插入节点，更新对应 level 的链表。

首先我们直接从高 level 开始跳，跳不了了就跳低一级的 level 即可找到需要插入的位置。
同时记录每一个 level 的当前位置之前的节点。（即可能需要更新后向指针的节点）。

Node *cur = head;  // current

for (int lev = level - 1; lev != -1; --lev) {
    while (cur->nxt[lev] && cur->nxt[lev]->key < key)
        cur = cur->nxt[lev];  // 存在满足要求的点就跳
    update[lev] = cur;
}

细节：可能当前 level 还没有到跳表可能达到的最高 level，但是当前这个节点随机到的 level 值在这两个数中间，所以需要将 level 到 MAX_LEVEL 这段补全为 head：

int lev = random_level(); // 当前节点的 level 值
if (lev > level) {
    for (int i = level; i < lev; ++i)
        update[i] = head;

    level = lev;
}

创建节点：

cur = create_node(lev, key);

执行插入操作，即对于每一层链表，更新前一个节点的指针，并让当前节点的后向指针指向后一个节点。

for (int i = lev - 1; i > -1; --i) {  // 普通链表插入操作
    cur->nxt[i] = update[i]->nxt[i];
    update[i]->nxt[i] = cur;
}

删除节点

和插入类似。

void erase(int key) {
    nodePointer cur = head;  // current

    for (int lev = level - 1; lev != -1; --lev) {
        while (cur->nxt[lev] && cur->nxt[lev]->key < key)
            cur = cur->nxt[lev];  // 存在满足要求的点就跳
        update[lev] = cur;
    }

    cur = cur->nxt[0];
    for (int i = 0; i < level; ++i)
        if (update[i]->nxt[i] == cur)
            update[i]->nxt[i] = cur->nxt[i];
        else
            break;

    while (level > 1 && !head->nxt[level - 1])  // 更新当前最大层数
        --level;
}

额外要注意的是，可能跳表的最高层就这一个节点，删了就没了，所以要判断并更新最大层数。

查找结点

实际上上面两个函数的第一部分就相当于查找。

bool find(int key) {
    Node* cur;

    for (int lev = level - 1; lev > -1; --lev)
        while (cur->nxt[lev] && cur->nxt[lev]->key < key)
            cur = cur->nxt[lev];  // 存在满足要求的点就跳

    return cur->nxt[0] ? cur->nxt[0]->key == key : false;
}

查找前驱后继的方法也差不多，前驱就是查找后直接返回 cur 而不是 cur->nxt[0]，后继可以跳到 cur->nxt[lev]->key <= key 的位置之后返回 cur->nxt[0]->key。最后的代码中有体现。

随机访问（按排名查询）

上面其实已经实现了跳表的基本功能了，但是显然，目前实现的功能都可以用平衡树替代，而且平衡树还能够按照数的排名查询。

由于维护的是有序序列，所以按照数的排名查询相当于随机访问。

接下来我们来实现跳表的随机访问。具体方法：维护每个后向指针的“跨度”（span），即它跳了几个节点。

形式化来说，设指针 \(ptr\) 从第 \(a\) 个节点指向第 \(b\) 个节点，则 \(ptr\) 的跨度为 \(b-a\)

除此以外，我们还需要维护一个长度 length，在每次 erase 和 insert 的时候加减一下就好了。

重写智能指针

啥是智能指针？不太清楚，但是我感觉维护一个 span 的指针实在太智能了！

我们需要给指针记录一个“跨度”，那就维护一个结构体作为指针，存原来的裸指针和跨度。

总的来说，需要构造函数并重载一个运算符，一个类型转换。

struct nodePointer {
    int span;
    Node* pointer;
    nodePointer() {
        this->pointer = nullptr; // 构造函数，将指针初始化为空
    }
    nodePointer(Node* node) {
        this->pointer = node;  // 如果提供了指针就用提供的
    }
    Node* operator->() {
        return pointer; // 指针原有的箭头运算符，访问 nodePointer->x 相当于访问 pointer->x
    }
    operator Node*() const {
        return pointer; // 智能指针转换为裸指针，直接返回 pointer 就好了
    }
};

不要在所有地方都使用 nodePointer，我们只在需要维护跨度的地方使用就好了。
编写代码时一定要注意类型的使用，比如说 unsigned long 不应乱用之类的。如果错误地更新 span，而你滥用了 nodePointer，可能就没那么容易找到问题了。

博主因为滥用 unsigned，跳表调了两天多。

需要维护跨度的地方只有跳转用的指针，即 nxt[]。

更改后的代码：

struct Node {
    int key, level;
    struct nodePointer {
        int span;
        Node* pointer;
        nodePointer() {
            this->pointer = nullptr; // 构造函数，将指针初始化为空
        }
        nodePointer(Node* node) {
            this->pointer = node;  // 如果提供了指针就用提供的
        }
        Node* operator->() {
            return pointer; // 指针原有的箭头运算符，访问 nodePointer->x 相当于访问 pointer->x
        }
        operator Node*() const {
            return pointer; // 智能指针转换为裸指针，直接返回 pointer 就好了
        }
    };
    nodePointer nxt[MAX_LEVEL];
} space[N];
using nodePointer = typename Node::nodePointer; // 为了方便书写，缩一下

重写插入函数

开一个数组记录每一层“上一个节点”的位置（利用跨度）。

int lst_pos[MAX_LEVEL];

然后在函数开头找位置的时候顺便把它处理出来：

for (int lev = level - 1; lev > -1; --lev) {
    // 更新 lst_pos
    if (lev == level - 1)
        lst_pos[lev] = 0; // 默认得是 0
    else
        lst_pos[lev] = lst_pos[lev + 1]; // 否则从上一层继承

    while (cur->nxt[lev] && cur->nxt[lev]->key < key) {
        lst_pos[lev] += cur->nxt[lev].span; // 更新
        cur = cur->nxt[lev];  // 存在满足要求的点就跳
    }
    update[lev] = cur;
}

插入的时候计算一下就好了。

然后 level 大于这个节点的指针跨度要加一。

结合代码理解。

for (int i = 0; i < lev; ++i) {  // 普通链表插入操作
    cur->nxt[i] = update[i]->nxt[i];
    update[i]->nxt[i].pointer = cur; // 这里不要直接让 nxt[i] = cur，因为后面还要用到 nxt[i].span
    cur->nxt[i].span = update[i]->nxt[i].span - (lst_pos[0] - lst_pos[i]); // lst_pos[0] 实际上就是上一个节点的位置
    update[i]->nxt[i].span = lst_pos[0] - lst_pos[i] + 1;
}
for (int i = lev; i < level; ++i) ++update[i]->nxt[i].span; // 维护高于新节点的指针的跨度

别忘了 ++length。

重写删除函数

把要删掉的指针的 span 加起来赋值给新指针就好了。

和 insert 一样，别忘记比当前节点高的指针跨度要 -1。

for (int i = 0; i < level; ++i)
    if (update[i]->nxt[i] == cur)
        update[i]->nxt[i].pointer = cur->nxt[i], update[i]->nxt[i].span += cur->nxt[i].span - 1;  // 跨度直接扔给前面那个指针就行了
    else
        --update[i]->nxt[i].span;

随机访问（按照排名查询）

int findrk(int k) {
    assert(k <= length && k); // k 不满足要求就异常
    Node* cur = head;
    for (int lev = level - 1; lev > -1 ; --lev)
        while (cur->nxt[lev] && k - cur->nxt[lev].span > 0) {
            k -= cur->nxt[lev].span;
            cur = cur->nxt[lev];  // 存在满足要求的点就跳
        }
    return cur->nxt[0]->key;
}

微调

我们可以对 MAX_LEVEL 和选取 level 的概率进行微调。

比如说下面的普通平衡树代码，把选取层数的 \(p\) 改成了 \(\frac 14\)，即 (rng() & 1) && (rng() & 1)，MAX_LEVEL 设为了 \(7\)，经测试这样比较快，在无快读不开 O2 的情况下吊打 Splay/FHQ/Treap，加了快读 O2 之后不知道为啥跑不过我之前写的指针 FHQ 了。另外数组 Treap 始终被吊打。这就是指针带给我的自信

复杂度分析

空间复杂度

设定了最高 level，所以空间复杂度只能是 \(\Theta(n)\) 的。

时间复杂度

见 OI Wiki

后记

实际上跳表最大的优点是能够顺序访问，这点是很多平衡树做不到的，FHQ Treap 分裂区间之后中序遍历是可以的，但是常数太大。

等我把跳表模板题搞出来，他们都得死！

完整代码

含类型泛化和封装成类。

另外实现了一些输入输出操作，自己看应该能看懂了。

#include <iostream>
#include <random>
#include <cassert>

#include <cstdlib>

using std::cin;
using std::cout;

std::random_device seed;
std::minstd_rand rng(seed());

#define N 106
#define MAX_LEVEL 32

using i32 = signed int;

template <typename T>
class skiplist {
private:
    i32 level;
    struct Node {
        T key;
        i32 level; // 千万的别用 unsigned
        struct nodePointer {
            i32 span; // 这个也千万他妈的别用 unsigned
            Node* pointer;
            nodePointer() {
                this->pointer = nullptr; // 构造函数，将指针初始化为空
            }
            nodePointer(Node* node) {
                this->pointer = node;  // 如果提供了指针就用提供的
            }
            Node* operator->() {
                return pointer; // 指针原有的箭头运算符，访问 nodePointer->x 相当于访问 pointer->x
            }
            operator Node*() const {
                return pointer; // 智能指针转换为裸指针，直接返回 pointer 就好了
            }
        };
        nodePointer nxt[MAX_LEVEL];
    } space[N];
    i32 bintop;
    using nodePointer = typename Node::nodePointer;
    Node *head, *tail, *tot, *rubbin[N / 4 * 3];

#define new_node() (bintop ? rubbin[bintop--] : ++tot)
#define del_node(x) (rubbin[++bintop] = (x))

    Node* create_node(const i32& level, const T& key) {
        Node* res = new_node();
        res->level = level;
        res->key = key;
        return res;
    }

    i32 random_level() {
        i32 res = 1;
        while (res < MAX_LEVEL && (rng() & 1)) {
            ++res;
        }
        return res;
    }

    Node* update[MAX_LEVEL];
    i32 lst_pos[MAX_LEVEL + 1];  // 每个 level 遍历到的最后一个元素的位置

public:
    skiplist() {
        tail = nullptr;
        level = 0;
        head = tot = space;
        bintop = 0;
        length = 0;
        lst_pos[MAX_LEVEL] = 0;
        for (i32 i = 0; i < MAX_LEVEL; ++i)
            head->nxt[i] = nullptr, head->nxt[i].span = 0;
    }

    void insert(const T& key) {
        Node* cur = head;  // current

        for (i32 lev = level - 1; lev > -1; --lev) {
            // 更新 lst_pos，这里由于已经把 lst_pos[MAX_LEVEL] 设为 0 了，所以不需要像上文一样特判
            lst_pos[lev] = lst_pos[lev + 1];

            while (cur->nxt[lev] && cur->nxt[lev]->key < key) {
                lst_pos[lev] += cur->nxt[lev].span;
                cur = cur->nxt[lev];  // 存在满足要求的点就跳
            }
            update[lev] = cur;
        }
        i32 lev = random_level();
        if (lev > level) {
            for (i32 i = level; i < lev; ++i) {
                update[i] = head;
                update[i]->nxt[i].span = length;  // 这层都还没有节点，直接从 head 指向尾部（nullptr），跨度为 length
            }
            level = lev;
        }

        cur = create_node(lev, key);

        for (i32 i = 0; i < lev; ++i) {  // 普通链表插入操作
            cur->nxt[i] = update[i]->nxt[i];
            update[i]->nxt[i].pointer = cur; // 这里不要直接让 nxt[i] = cur，因为后面还要用到 nxt[i].span
            cur->nxt[i].span = update[i]->nxt[i].span - (lst_pos[0] - lst_pos[i]); // lst_pos[0] 实际上就是上一个节点的位置
            update[i]->nxt[i].span = lst_pos[0] - lst_pos[i] + 1;
        }
        for (i32 i = lev; i < level; ++i) ++update[i]->nxt[i].span;

        ++length;
    }

    void erase(const T& key) {
        Node* cur = head;  // current

        for (i32 lev = level - 1; lev != -1; --lev) {
            while (cur->nxt[lev] && cur->nxt[lev]->key < key)
                cur = cur->nxt[lev];  // 存在满足要求的点就跳
            update[lev] = cur;
        }

        cur = cur->nxt[0];
        for (i32 i = 0; i < level; ++i)
            if (update[i]->nxt[i] == cur)
                update[i]->nxt[i].pointer = cur->nxt[i].pointer, update[i]->nxt[i].span += cur->nxt[i].span - 1;  // 跨度直接扔给前面那个指针就行了
            else
                --update[i]->nxt[i].span;

        while (level > 1 && !head->nxt[level - 1])  // 更新当前最大层数
            --level;
        del_node(cur);
        --length;
    }

    bool find(const T& key) {
        Node* cur = head;

        for (i32 lev = level - 1; lev > -1; --lev)
            while (cur->nxt[lev] && cur->nxt[lev]->key < key)
                cur = cur->nxt[lev];  // 存在满足要求的点就跳

        return cur->nxt[0] ? cur->nxt[0]->key == key : false;
    }

    T findrk(i32 k) {
        assert(k <= length && k); // k 不满足要求就异常
        Node* cur = head;
        for (i32 lev = level - 1; lev > -1 ; --lev)
            while (cur->nxt[lev] && k - cur->nxt[lev].span > 0) {
                k -= cur->nxt[lev].span;
                cur = cur->nxt[lev];  // 存在满足要求的点就跳
            }
        return cur->nxt[0]->key;
    }

    i32 length;
};

skiplist<i32> list;

#include <string>

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    i32 n, tx;
    cin >> n;
    for (i32 i = 1; i <= n; ++i) {
        cin >> tx;
        list.insert(tx);
    }
    std::string s;
    while (cin >> s) {
        switch (s[0]) {
            case ('l'): cout << list.length << std::endl; break;
            case ('i'):
            case ('a'):
                cin >> tx;
                list.insert(tx);
                break;
            case ('d'):
            case ('r'): {
                cin >> tx;
                if (list.find(tx))
                    list.erase(tx);
                else
                    cout << "该值不存在" << std::endl;
                break;
            }
            case ('f'):
                cin >> tx;
                cout << (list.find(tx) ? "存在" : "不存在") << std::endl;
                break;
            case ('g'):
                cin >> tx;
                cout << list.findrk(tx) << std::endl;
                break;
            default: cout << "未知命令" << std::endl;
        }
    }

    return 0;
}

参考文献

《跳跃表数据结构与算法分析》 纪卓志 George

《跳表》 OI Wiki

推荐阅读

《关于 skip list 的一些扩展想法》

标签：key,nxt,cur,level,实现,手把手,跳表,lev,指针
From： https://www.cnblogs.com/tibrella/p/skip-list.html

相关文章

  • destoon上做纯js实现html指定页面导出word
    因为最近做了范文网站需要，所以要下载为word文档，如果php进行处理，很吃后台服务器，所以想用前端进行实现。查询github发现，确实有这方面的插件。js导出word文档所需要的两个插件：12FileSaver.jsjquery.wordexport.js首先引入：1234<!--生成wo......
  • Python实现自动生成四则运算题目和答案检测
    这个作业属于哪个课程软件工程这个作业要求在哪里结对项目这个作业的目标实现自动生成四则运算题目功能，以及给定题目和答案、判断答案对错的功能本项目上传至个人GitHub：yulinnn/PythonProject_FourOperations项目需求题目：实现一个自动生成小学四则运算题目的......
  • Java多线程实现生产者与消费者模型
    java多线程实现生产者与消费者模型//测试类publicclassTestPC{publicstaticvoidmain(String[]args){SynContainercontainer=newSynContainer();newThread(newProductor(container),"生产者线程").start();newThread(newConsum......
  • MySQL的锁实现
    数据库锁机制 一.数据库锁的类型和细度   （一）类型     1. 共享锁：读锁，不同事务可以同是读取加共享锁的数据，但是不能同时加写锁和写操作  forshare     2.排他锁：写锁，不同事务，不可以同时读取加锁的资源进行写入  forupdate   （二）细度......
  • 【详解】Spring Boot + Mybatis-Plus实现CRUD，轻松玩转接口操作！
    ......
  • 敏捷开发的实施要素和实现敏捷的实际改进
    ​敏捷开发的实施要素如下：个体和交互：胜过过程和工具。可以工作的软件：胜过面面俱到的文档。客户合作：胜过合同谈判。响应变化：胜过遵循计划。敏捷开发过程是一个增量的、迭代的过程，责任人、开发人员和用户要能够共同维持其步调稳定延续。实现敏捷的实际改进可以从以下方面入......
  • 用C#实现DES加密解密
    using  System;  using  System.Security.Cryptography;  using  System.Text;  using  System.IO;    namespace  Common  ...{          /** <summary>           /// DESEncrypt加密解密算法。           ///</summa......
  • 赛事星平台的作答脚本Python实现(适用于刷时间)
    灵感来源:白嫖某文理的一次答题竞赛,前一百名有奖品正好缺个蓝牙耳机索性就刷个时间白嫖一波吧.咳咳,正式开始分享咯.准备工作:谷歌浏览器以及自带开发者工具页面分析:由于此次白嫖活动已经结束,就采用其他竞赛URL进行分析,原理相同.URL:https://saishi.cnki.net/MatchInde......
  • 堆的原理以及实现O(lgn)
    大家好，我是蓝胖子，我一直相信编程是一门实践性的技术，其中算法也不例外，初学者可能往往对它可望而不可及，觉得很难，学了又忘，忘其实是由于没有真正搞懂算法的应用场景，所以我准备出一个系列，囊括我们在日常开发中常用的算法，并结合实际的应用场景，真正的感受算法的魅力。今天我们就来看看......
  • 【Java】SpringBoot邮件发送实现
    Springboot3邮件发送哔哩哔哩萌狼蓝天微信公众号萌狼蓝天依赖<dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-mail</artifactId></dependency>配置这里我用的是网易免费企......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99