C++如何实现一个跳表（Skip List）？C++概率数据结构实战【算法】

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

C++如何实现一个跳表（Skip List）？C++概率数据结构实战【算法】

2025-12-13

浏览次数：次

返回列表

跳表是一种概率型多层链表结构，平均查找复杂度O(log n)，通过随机升层维持平衡，支持高效插入、删除与并发操作，C++需手写实现。

c++如何实现一个跳表（skip list）？c++概率数据结构实战【算法】

跳表（Skip List）是一种概率型数据结构，用多层链表实现快速查找，平均时间复杂度为 O(log n)，实现比平衡树简单，且天然支持并发。C++ 标准库没有内置跳表，但可以手写一个轻量、可扩展的版本。

核心设计思路：分层+随机提升

跳表本质是“带索引的有序链表”。底层是完整有序链表（Level 0），上层是稀疏子集（每层节点数约减半），通过随机决定是否“升层”来维持结构平衡——不靠旋转或重平衡，靠概率摊平高度。

关键点：

每个节点包含一个值 + 一组指针（指向各层的后继），层数在插入时随机生成（如抛硬币直到出现反面，层数 = 连续正面次数 + 1）
所有层共享同一套节点（不是复制值），只是不同层的指针视图不同
查找从最高层开始，向右走不动就下一层，类似“先坐快线再换慢车”
删除只需断开各层对应指针，无需调整结构

简易可运行的 C++ 跳表实现（支持插入/查找/删除）

以下是一个精简但完整、带注释的单文件实现（C++17）：

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
<p>template<typename T>
class SkipList {
private:
struct Node {
T value;
std::vector<Node*> next; // next[i] 指向第 i 层的后继
explicit Node(const T& v, size_t level) : value(v), next(level, nullptr) {}
};</p><pre class='brush:php;toolbar:false;'>Node* head;
size_t max_level;
mutable std::mt19937 rng;

// 抛硬币：返回 [1, max_level] 的随机层数（概率 ~1/2^k）
size_t random_level() const {
    size_t lvl = 1;
    std::uniform_int_distribution<int> dist(0, 1);
    while (dist(rng) == 1 && lvl < max_level) ++lvl;
    return lvl;
}

public: explicit SkipList(size_t max_lvl = 16) : max_level(max_lvl), rng(std::random_device{}()) { head = new Node(T{}, max_level); // 哨兵头节点，值不重要 }

~SkipList() {
    while (head) {
        Node* tmp = head;
        head = head->next[0];
        delete tmp;
    }
}

bool find(const T& key) const {
    Node* x = head;
    for (int i = max_level - 1; i >= 0; --i) {
        while (x->next[i] && x->next[i]->value < key)
            x = x->next[i];
    }
    x = x->next[0];
    return x && x->value == key;
}

void insert(const T& key) {
    std::vector<Node*> update(max_level, head);
    Node* x = head;

    // 记录每层最后一个小于 key 的节点（用于后续链接）
    for (int i = max_level - 1; i >= 0; --i) {
        while (x->next[i] && x->next[i]->value < key)
            x = x->next[i];
        update[i] = x;
    }

    size_t lvl = random_level();
    Node* newNode = new Node(key, lvl);

    // 将新节点插入到各层
    for (size_t i = 0; i < lvl; ++i) {
        newNode->next[i] = update[i]->next[i];
        update[i]->next[i] = newNode;
    }
}

bool erase(const T& key) {
    std::vector<Node*> update(max_level, nullptr);
    Node* x = head;

    for (int i = max_level - 1; i >= 0; --i) {
        while (x->next[i] && x->next[i]->value < key)
            x = x->next[i];
        update[i] = x;
    }

    x = x->next[0];
    if (!x || x->value != key) return false;

    for (size_t i = 0; i < x->next.size(); ++i) {
        update[i]->next[i] = x->next[i];
    }
    delete x;
    return true;
}

};

使用示例与注意事项

你可以这样测试：

Mistral AI

Mistral AI被称为“欧洲版的OpenAI”，也是目前欧洲最强的 LLM 大模型平台

182 查看详情 Mistral AI

int main() {
    SkipList<int> sl;
    sl.insert(3); sl.insert(6); sl.insert(7);
    sl.insert(9); sl.insert(12); sl.insert(19);
<pre class='brush:php;toolbar:false;'>std::cout << sl.find(7) << "\n"; // 1
std::cout << sl.find(5) << "\n"; // 0
sl.erase(6);
std::cout << sl.find(6) << "\n"; // 0

}

注意点：