数据结构：跳表

跳表

在传统的链表中，不论单链表还是双链表，查询时都要O(N)的时间复杂度，就算是一个有序链表，由于无法像数组一样定址，无法进行二分查找。

为此，有人提出了增加链表的指针域，使其可以进行二分查找：

在这里插入图片描述

假设对于一个有序链表，每相邻的两个节点，升高一层，增加一个指针，让指针指向下一个升高的节点，也就是下面的链表。

如果要查找21，那么从3出发，从高层往底层查找。先在第二层查找，21 > 7，所以目标节点在7后面，21 > 12、21 > 19以此类推。直到查询到25，发现21 < 25，说明要查找的系欸但在[19, 25]之间，下降一层。随后去19的第一层的后一个节点查找，21 == 21找到目标元素。

这个查询过程中，跳过了6 9 17这几个只低层节点，快速的定位目标节点的范围，其实就是一个二分思想。

以此类推，还可以让每4个节点再升高一层：

在这里插入图片描述

甚至每8个节点再升高一层，也就是每到隔 2 n 2^{n} 2n的节点层数增加一层。这样就是一个完全的二分查找了，查询时间复杂度为 O ( l o g N ) O(logN) O(logN)。

但是这样的结构有很大的问题，那就是不好删除节点。如果要插入或删除某个节点，此时后续每个节点的位置都变化了，那么节点对应的层数也要进行变化。而层数变化之后，又要维护错综复杂的指针关系，因此这种严格的二分结构没有被推广。

为了避免这种问题，设计者做了一个大胆的处理，不再严格规定每个位置的节点的层数，而是插入节点时随机出一个层数。这样插入与删除都不用管其它节点是多少层，自己的层数完全随机。

在这里插入图片描述

图中红色路径是查找21，绿色路径是在查找26。在查找过程中，会跳过很多节点，因此称为skipList 跳表。

刚刚提到，跳表每个节点的层数都是随机的，这会不会太随便了，会不会导致效率很低？

其实跳表的随机是有固定的算法的，如下：

int getRandomLevel()
{
    int level = 1;

    while (rand() < RAND_MAX * p)
        level++;

    return level;
}

跳表的初始层数为1，随后进入一个循环判断，每次循环有p的概率增加一层，如果本次没有增加层，那么终止循环。

比如说第一次循环：

  1. 有p的概率变成2层，并进入下一轮循环判定
  2. 有 1 - p的概率不增加层，此时跳出循环，最终层数就是1

如果可以进入第二次循环：

  1. 有p的概率变成3层，并进入下一轮循环判定
  2. 有 1 - p的概率不增加层，此时跳出循环，最终层数就是2

以此类推。另外的，跳表还要给出一个最高层数的限制，如果层数到达最高层数，不再进行下一轮判定，这一步在上述代码中没有体现。

由此可得：

  1. 层数为1的概率为 1 − p 1 - p 1−p
  2. 层数为2的概率为 p × ( 1 − p ) p\times(1-p) p×(1−p)，第一轮加层概率为 p，第二轮不加层概率为 (p - 1)
  3. 层数为3的概率为 p 2 × ( 1 − p ) p^{2}\times(1-p) p2×(1−p)，前两轮加层概率为 p 2 p^{2} p2，第三轮不加层概率为 (p - 1)
  4. 以此类推…
  5. 层数为n的概率为 p n − 1 × ( 1 − p ) p^{n-1}\times(1-p) pn−1×(1−p)，前n-1轮加层概率为 p n − 1 p^{n-1} pn−1，第n轮不加层概率为 (p - 1)

计算可得，跳表的平均层数为：

1 1 − p \frac{1}{1-p} 1−p1​

在Redis中，p = 0.25，最大层数不超过32层，此时平均每个节点的层数是4/3层。

实现

类架构

  • 节点类
template <typename T>
struct SkipListNode
{
    T _val;
    vector<SkipListNode*> _nextNodes;

    SkipListNode(T val, int level)
        : _val(val)
        , _nextNodes(level, nullptr)
    {}
};
  1. val：当前节点存储的值
  2. _nextNodes：动态数组，存储指向下一个节点的指针，每一层的下一个节点可能不同
  • 跳表类
template <typename T>
class SkipList
{
    using Node = SkipListNode<T>;

private:
    Node* _head;   // 头节点
    int _maxLevel; // 最大层高
    double _p;     // 概率
    int _curLevel; // 当前最大层高
    int _size;	   // 节点个数
};
  1. _head：指向头节点的指针
  2. _maxLevel：单个节点的最大层数
  3. _p：单轮循环，节点增加层的概率
  4. _curLevel：当前所有节点中的最大层高
  5. _size：跳表的元素个数

构造函数

构造函数如下：

SkipList(int maxLevel = 32, double p = 0.25)
    : _maxLevel(maxLevel)
    , _p(p)
    , _curLevel(0)
    , _size(0)
{
    srand((unsigned int)time(nullptr));
    _head = new Node(T(), _maxLevel);
}

在构造函数中，允许用户自定义概率和最大层数，默认情况maxLevel = 32，p = 0.25。在初始化列表中完成成员变量的初始化。

由于后续要计算随机数，在构造函数中srand((unsigned int)time(nullptr))将时间作为随机数种子。

随后构造一个头节点，这个节点作为哨兵不存储实际数据。头节点的层数指定为最大层数。

析构函数

析构函数如下：

~SkipList()
{
    Node* del = _head;
    Node* tmp = nullptr;

    while (del)
    {
        tmp = del->_nextNodes[0];
        delete del;
        del = tmp;
    }
}

析构函数需要从头到尾进行释放节点，此时直接遍历链表，并且只遍历第一层_nextNodes[0]。因为所有节点都有第一层，所以遍历第一层一定可以释放掉所有节点。

查找

基于跳表的两大特性：有序、分层。其实查找过程中，每次行动只有以下两种选择：

  1. 在同层向右移动
  2. 向下一层移动

比如查找21的过程：

在这里插入图片描述

红色路径就是21的查找路径。

  1. 从头节点第4层出发，查看同层的下一个节点6，21 >= 6说明要找的节点在6之后，向右移动
  2. 从6的第4层出发，查看同层的下一个节点NULL，说明当前层没有下一个节点了，只能向下移动
  3. 从6的第3层出发，查看同层的下一个节点25，21 < 25说明要找的节点在25之前，向下移动
  4. 从6的第2层出发，查看同层的下一个节点9，21 >= 9说明要找的节点在9之后，向右移动
  5. 从9的第2层出发，查看同层的下一个节点17，21 >= 17说明要找的节点在17之后，向右移动
  6. 从17的第2层出发，查看同层的下一个节点25，21 < 25说明要找的节点在25之前，向下移动
  7. 从17的第1层出发，查看同层的下一个节点19，21 >= 19说明要找的节点在19之后，向右移动
  8. 从19的第1层出发，查看同层的下一个节点21，21 >= 21说明要找的节点在21之后，向右移动
  9. 从21的第1层出发，查看同层的下一个节点25，21 < 25说明要找的节点在25之前，向下移动
  10. 到达第0层，说明已经查找完毕，当前所在节点21 == 21，成功找到节点

假设要查找20，前7步相同，后两步：

  1. 从19的第1层出发，查看同层的下一个节点21，20 <=21说明要找的节点在21之前，向下移动
  2. 到达第0层，说明已经查找完毕，当前所在节点19 != 20，说明节点20不存在

可以总结出查找逻辑：

  1. 同层下一个节点为空指针，向下移动一层
  2. 目标值大于等于同层下一个节点的值，移动至同层的下一个节点
  3. 目标值小于同层下一个节点的值，向下移动一层
  4. 当到达第0层，判断节点值是否是目标值

代码：

bool find(T val)
{
    int level = _curLevel - 1; // 获得当前的最高层
    Node* cur = _head; // 记录当前节点

    while (level >= 0) // 当 level 到达第0层，查找完毕
    {
        if (cur->_nextNodes[level] != nullptr && val >= cur->_nextNodes[level]->_val)
            cur = cur->_nextNodes[level]; // 向同层的下一个节点移动
        else
            level--; // 向下移动一层
    }

    return cur != nullptr && cur->_val == val;
}

首先要注意的是，_nextNodes是一个数组，_nextNodes[0]代表的是第一层，也就是说下标和层数之间有一个错位。所以最开始level = _curLevel - 1要进行减一操作。

在while(level >= 0)同理，level = 0时，是在第一层而不是第零层，继续循环。

cur->_nextNodes[level]代表同层的下一个节点，因为每次比较，都要和同层的下一个节点比较。比较之前，先判断下一个节点是否为空，防止访问空指针。

最后跳出循环时，查看cur存储的值是否是目标值，如果是，那么该元素存在，反之则不存在。

插入

如图：

在这里插入图片描述

当插入一个新节点时，该节点的前后指针都要改变，也就是图中固定红色指针。那么在找到插入位置后，要把插入位置每一层的前一个节点记录下来。

查找每一层的前一个节点：

vector<Node*> findPrev(T val)
{
    vector<Node*> prevNodes(_maxLevel, _head); // 前一个节点的数组

    int level = _curLevel - 1; // 从当前最高层出发
    Node* cur = _head;

    while (level >= 0)
    {
        if (cur->_nextNodes[level] && val > cur->_nextNodes[level]->_val)
        {
            cur = cur->_nextNodes[level]; // 向右移动
        }
        else
        {
            prevNodes[level] = cur; // 记录该层的前一个节点为cur
            level--; // 向下移动
        }
    }

    return prevNodes;
}

该函数接受一个val，返回val的每一层的前一个节点。 prevNodes(_maxLevel, _head)用于存储返回值，元素初始化为_head，即每个节点默认的前一个节点为_head，如果后续新节点的层数超出了当前最大层数，此时前一个节点为_head。

level = _curLevel - 1随后从当前的最高层出发，查找插入位置。

在这里插入图片描述

查找每一层前一个节点时，只要层数下降，说明当前节点就是该层的前一个节点。

比如插入15，从head出发，到达节点6的第四层，此时第四层下一个节点为NULL，向下移动，此时15在第四层的前一个节点为6。

从节点6的第三层出发，第三层下一个节点为25，25 > 15向下移动，此时15在第三层的前一个节点为6。

后续同理，在第二层的前一个节点为9，第一层的前一个节点为12。

在上述代码中，有一个小细节，那就是val > cur->_nextNodes[level]->_val)，在find中，此处是大于等于，而这里改成了大于。因为要找前一个节点，在下一个节点值等于目标值的时候，要向下移动，而不是向后移动。

插入代码：

bool insert(const T& val)
{
    vector<Node*> prevNodes = findPrev(val);
    if (prevNodes[0]->_nextNodes[0] != nullptr
        && prevNodes[0]->_nextNodes[0]->_val == val)
        return false; // 已存在

    int level = getRandomLevel(); // 获取随机层数
    _curLevel = max(_curLevel, level); // 更新最大层数

    Node* node = new Node(val, level); // 创建新节点

    for (int i = 0; i < level; i++)
    {
        node->_nextNodes[i] = prevNodes[i]->_nextNodes[i];
        prevNodes[i]->_nextNodes[i] = node;
    }

    _size++;
    return true;
}

插入之前，先判断目标值是否已经存在，由于prevNodes 存储的是每一层的前一个节点，所以prevNodes[0]->_nextNodes[0]才是要插入的位置，此时如果prevNodes[0]->_nextNodes[0]->_val == val，说明要插入的值原先就存在，直接返回false。

随后通过getRandomLevel函数获取一个随机层数。如果随机的层数超过了当前最大层，更新当前的最大层数。

然后通过val和随机层数level创建一个节点。从新节点的最高层往下，node->_nextNodes[i] = prevNodes[i]->_nextNodes[i]将新节点的下一个节点，指向原先前一个节点的下一个节点。prevNodes[i]->_nextNodes[i] = node将前一个节点的下一个节点，设为新节点。这和链表的插入是一样的，只是因为有一个分层的概念，所以这里比较抽象。

其实就是：

node->next = prev->next;
prev->next = node;

这样就很好理解了。

完成前后节点的指针关系维护，插入就完成了，最后_size++表示总节点数增加。

删除

理解了插入，删除也很简单了，如图：

在这里插入图片描述

同理，删除节点，只需要注意维护每一层的前后指针关系即可。

删除代码：

bool erase(const T& val)
{
    vector<Node*> prevNodes = findPrev(val);
    if (prevNodes[0]->_nextNodes[0] == nullptr
        || prevNodes[0]->_nextNodes[0]->_val != val)
        return false; // 不存在

    Node* del = prevNodes[0]->_nextNodes[0]; // 记录被删除的节点

    for (int i = 0; i < del->_nextNodes.size(); i++)
        prevNodes[i]->_nextNodes[i] = del->_nextNodes[i]; // 维护指针关系

	// 更新最大层数

    delete del;
    _size--;
    return true;
}

首先判断被删除的节点是否存在，这个if判断条件和插入是刚好相反的。如果目标值不存在，就不删除，返回false。

随后Node* del = prevNodes[0]->_nextNodes[0]记录要删除的节点。这里使用prevNodes[0]是因为不确定要删除的节点是多少层，但是它至少有1层，所以拿第一层的下一个节点一定可以找到要删除的节点。

随后一个for循环维护指针关系，相当于以下代码：

prev->next = del->next;

最后delete del删除节点，最后_size--表示目标节点少一个。

但是这还有一个问题，那就是如果删除节点之后，层高降低了：

在这里插入图片描述

此处6作为唯一一个四层的节点，删除后整个跳表的高度都降低为了3，所以在删除操作的最后，还少了一步检测当前的最大层高。也就是以上代码的// 更新最大层数位置。

更新层高：

if (del->_nextNodes.size() == _curLevel) // 被删除的节点，层高和当前的最大层高一致
{
    for (int i = 0; i < _maxLevel; i++)
    {
        if (_head->_nextNodes[i] == nullptr) // 当前层 _head 下一个节点为空
        {
            _curLevel = i; // 更新层高
            break;
        }
    }
}

更新层高很简单，让_head节点从最底层出发，向上检测，如果某一层_head的下一个节点为nullptr，说明没有更高层了，此时层高就是该层-1。

首先通过if判断，被删除节点的层高是否是最大层高，如果被删除节点的层高不是最大层高，那么就算被删除了也不会影响最大层高。

随后进入for循环，从最底层开始向上检测，当第一次检测到_head的下一个节点为空，更新层高。_curLevel = i，此处注意是i而不是i - 1，因为_nextNodes[i]层的下一个节点为空，说明_nextNodes[i]的低一层为最高层，而由于下标与层高的错位关系，_nextNodes[i]其实是第i + 1层，它的低一层是i + 1 - 1 = i，所以_curLevel = i。

总代码

  • SkipList.hpp：
#pragma once
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <time.h>

using namespace std;

template <typename T>
struct SkipListNode
{
    T _val;
    vector<SkipListNode*> _nextNodes;

    SkipListNode(T val, int level)
        : _val(val)
        , _nextNodes(level, nullptr)
    {}
};

template <typename T>
class SkipList
{
    using Node = SkipListNode<T>;
public:

    SkipList(int maxLevel = 32, double p = 0.25)
        : _maxLevel(maxLevel)
        , _p(p)
        , _curLevel(0)
        , _size(0)
    {
        srand((unsigned int)time(nullptr));
        _head = new Node(T(), _maxLevel);
    }

    ~SkipList()
    {
        Node* del = _head;
        Node* tmp = nullptr;

        while (del)
        {
            tmp = del->_nextNodes[0];
            delete del;
            del = tmp;
        }
    }

    bool find(T val)
    {
        int level = _curLevel - 1;
        Node* cur = _head;

        while (level >= 0)
        {
            if (cur->_nextNodes[level] && val >= cur->_nextNodes[level]->_val)
                cur = cur->_nextNodes[level];
            else
                level--;
        }

        return cur != nullptr && cur->_val == val;
    }

    vector<Node*> findPrev(T val)
    {
        vector<Node*> prevNodes(_maxLevel, _head);

        int level = _curLevel - 1;
        Node* cur = _head;

        while (level >= 0)
        {
            if (cur->_nextNodes[level] && val > cur->_nextNodes[level]->_val)
            {
                cur = cur->_nextNodes[level];
            }
            else
            {
                prevNodes[level] = cur;
                level--;
            }
        }

        return prevNodes;
    }

    int getRandomLevel()
    {
        int level = 1;

        while (rand() < RAND_MAX * _p && level < _maxLevel)
            level++;

        return level;
    }

    bool insert(const T& val)
    {
        vector<Node*> prevNodes = findPrev(val);
        if (prevNodes[0]->_nextNodes[0] != nullptr
            && prevNodes[0]->_nextNodes[0]->_val == val)
            return false; // 已存在

        int level = getRandomLevel();
        _curLevel = max(_curLevel, level);

        Node* node = new Node(val, level);

        for (int i = 0; i < level; i++)
        {
            node->_nextNodes[i] = prevNodes[i]->_nextNodes[i];
            prevNodes[i]->_nextNodes[i] = node;
        }

        _size++;
        return true;
    }

    bool erase(const T& val)
    {
        vector<Node*> prevNodes = findPrev(val);
        if (prevNodes[0]->_nextNodes[0] == nullptr
            || prevNodes[0]->_nextNodes[0]->_val != val)
            return false; // 不存在

        Node* del = prevNodes[0]->_nextNodes[0];

        for (int i = 0; i < del->_nextNodes.size(); i++)
            prevNodes[i]->_nextNodes[i] = del->_nextNodes[i];

        if (del->_nextNodes.size() == _curLevel)
        {
            for (int i = 0; i < _maxLevel; i++)
            {
                if (_head->_nextNodes[i] == nullptr)
                {
                    _curLevel = i;
                    break;
                }
            }
        }

        delete del;
        _size--;
        return true;
    }

    void print()
    {
        vector<vector<T>> show(_curLevel, vector<T>(_size, 0));
        Node* cur = _head->_nextNodes[0];
            
        for (int i = 0; i < _size; i++)
        {
            for (int j = 0; j < cur->_nextNodes.size(); j++)
                show[j][i] = cur->_val;

            cur = cur->_nextNodes[0];
        }

        for (int i = _curLevel - 1; i >= 0; i--)
        {
            for (int j = 0; j < _size; j++)
            {
                if (show[i][j] != T())
                    printf("%2d", show[i][j]);
                else
                    printf("  ");
            }
            printf("\n");
        }
    }

private:
    Node* _head;      // 头节点
    int _maxLevel; // 最大层高
    double _p;        // 概率
    int _curLevel; // 当前最大层高
    int _size;
};
  • test.cpp：
#include <iostream>
#include "SkipList.hpp"

using namespace std;

int main()
{
    SkipList<int> sk;

    sk.insert(1);
    sk.insert(2);
    sk.insert(3);
    sk.insert(4);
    cout << "测试重复插入:" << endl;
    cout << "第一次:" << sk.insert(5) << endl;
    cout << "第二次:" << sk.insert(5) << endl;
    sk.insert(6);
    sk.insert(7);
    sk.insert(8);
    sk.insert(9);
    cout << "-------------------" << endl;
    cout << "插入1-9:" << endl;
    sk.print();
    cout << "-------------------" << endl;
    cout << "查询1:" << sk.find(1) << endl;
    cout << "查询2:" << sk.find(2) << endl;
    cout << "查询8:" << sk.find(8) << endl;
    cout << "查询9:" << sk.find(9) << endl;
    cout << "查询12:" << sk.find(12) << endl;
    cout << "查询256:" << sk.find(256) << endl;
    cout << "查询-5:" << sk.find(-5) << endl;
    cout << "-------------------" << endl;
    cout << "删除7:" << sk.erase(7) << endl;
    cout << "重复删除7:" << sk.erase(7) << endl;
    sk.print();
    cout << "-------------------" << endl;
    cout << "删除3:" << sk.erase(7) << endl;
    sk.erase(3);
    sk.print();
    cout << "-------------------" << endl;

    return 0;
}
# 数据结构
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

全家桶集齐！Qwen3.5四款小模型上线魔乐社区，附昇腾全套实践教程

avatar 魔乐社区

Pont - 搭建前后端之桥：高效、灵活的接口管理工具

Pont 是一款强大的数据服务层解决方案，它能够帮助开发者快速搭建前后端之间的桥梁，实现接口的高效管理和代码自动生成。无论是新手还是有经验的开发者，都能通过 Pont 轻松处理接口文档、生成类型安全的 API 代码，从而显著提升开发效率。[![Pont 工具标志](https://raw.gitcode.com/gh_mirrors/po/pont/raw/3f1b7d4bbba3fd2dda

avatar 魔乐社区

如何快速上手 hvac：HashiCorp Vault Python 客户端零基础入门指南

**hvac** 是 HashiCorp Vault 的 Python 3.X 客户端库，专为开发者提供简单高效的 Vault 交互方式。无论你是需要管理密钥、配置身份验证，还是实现安全的秘密数据存储，hvac 都能帮助你轻松搞定 Vault 的各项操作。本文将带你零基础快速入门，从安装到基础操作，让你在几分钟内即可上手使用这个强大的工具。[![hvac 客户端 Logo](https://r

avatar 魔乐社区