c++如何实现一个跳表(Skip List)_c++替代平衡树的高效数据结构【源码】

夏宇大大_1966

夏宇大大_1966

2025-12-13

478人浏览

原创

跳表是一种概率性多层链表结构,平均查找复杂度O(log n),通过随机提升和分层索引实现高效操作,比平衡树更易实现。

c++如何实现一个跳表(skip list)_c++替代平衡树的高效数据结构【源码】

<p>跳表(Skip List)是一种概率性数据结构,用多层链表实现快速查找,平均时间复杂度为 O(log n),最坏 O(n),但实践中非常稳定,且比红黑树、AVL 等平衡树更易实现和调试。C++ 中无需依赖复杂旋转逻辑,只需维护多级前向指针即可。</p>

<h3>核心设计思路:分层 + 随机提升</h3>
<p>跳表本质是“带索引的有序链表”:底层是完整有序链表(Level 0),上层是稀疏子集(每层节点以约 50% 概率“晋升”到上一层)。查找时从最高层开始向右跳,遇到过大值就下移,最终在底层定位目标。</p>
<p>关键点:</p>
  • 每个节点不是固定层数,而是插入时随机决定层数(如用 rand() % 2 == 0 不断提升,直到失败,最大层数可设上限,如 32)
  • 所有层共享同一组键值,仅指针结构分层
  • 头节点(head)需初始化为 max_level 层,每层 next 指针初始为 nullptr
  • 为简化边界处理,可设哨兵尾节点(或用 nullptr 表示结尾)

节点定义与内存管理

节点需存储 key、value(支持 map 语义)、以及动态长度的 next 指针数组:

<font size="2">struct SkipListNode {
    int key;
    std::string value;  // 可泛化为 template <typename v>
    std::vector<skiplistnode> next;

    SkipListNode(int k, const std::string& v, int level) 
        : key(k), value(v), next(level, nullptr) {}
};</skiplistnode></typename></font>

不推荐用 raw new/delete 手动管理 —— 可封装在类内用 std::vector 或 std::unique_ptr 统一释放;若追求极致性能,可用内存池(但初版跳表建议先忽略)。

logos-node
logos-node

在 Linux x86_64 上安装、更新或检查 Logos 区块链测试网验证节点。用于用户需要搭建 Logos 节点时使用。

下载

插入与查找的核心逻辑

查找(search)是插入/删除的基础:记录每层最后一个小于 key 的节点(update 数组),用于后续链接修复:

<font size="2">SkipListNode* search(int key) {
    auto x = head;
    for (int i = current_level - 1; i >= 0; i--) {
        while (x->next[i] && x->next[i]->key next[i];
        }
    }
    x = x->next[0];  // 落到 level 0,检查是否命中
    return (x && x->key == key) ? x : nullptr;
}</font>

插入(insert)流程:

  • 先执行 search 过程,同时记录每层“前驱节点”到 update[i]
  • 生成新节点,层数 random_level()(如:while (rand() & 1 && lvl
  • 更新 current_level(若新层数更高)
  • 逐层设置新节点 next[i] = update[i]->next[i],再令 update[i]->next[i] = 新节点

完整可运行精简版(支持 int→string 映射)

<font size="2">#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

struct SkipListNode {
    int key;
    std::string value;
    std::vector<skiplistnode> next;

    SkipListNode(int k, const std::string& v, int level) 
        : key(k), value(v), next(level, nullptr) {}
};

class SkipList {
    SkipListNode* head;
    int current_level;
    const int max_level = 16;
    std::mt19937 rng{std::random_device{}()};

    int random_level() {
        int lvl = 1;
        std::bernoulli_distribution d(0.5);
        while (d(rng) && lvl next[0];
            delete x;
            x = next;
        }
    }

    void insert(int key, const std::string& value) {
        std::vector<skiplistnode> update(max_level, head);
        auto x = head;

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

        x = x->next[0];
        if (x && x->key == key) {
            x->value = value;  // 更新已存在 key
            return;
        }

        int lvl = random_level();
        if (lvl > current_level) {
            for (int i = current_level; i next[i] = update[i]->next[i];
            update[i]->next[i] = x;
        }
    }

    std::string find(int key) {
        auto x = head;
        for (int i = current_level - 1; i >= 0; i--) {
            while (x->next[i] && x->next[i]->key next[i];
        }
        x = x->next[0];
        return (x && x->key == key) ? x->value : "";
    }
};

// 使用示例
int main() {
    SkipList sl;
    sl.insert(3, "three");
    sl.insert(1, "one");
    sl.insert(5, "five");
    std::cout </skiplistnode></skiplistnode></algorithm></random></vector></iostream></font>

该实现支持重复 key 的覆盖写入,无锁(单线程安全),内存自动释放。如需并发,可在关键路径加 std::shared_mutex(读多写少场景下性能仍优于平衡树锁粒度)。

基本上就这些 —— 跳表不复杂但容易忽略层级同步和内存释放细节,掌握 update 数组和 random_level 就抓住了主干。

C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!

相关文章

c++速学教程(入门到精通)
c++速学教程(入门到精通)

c++怎么学习?c++怎么入门?c++在哪学?c++怎么学才快?不用担心,这里为大家提供了c++速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

node c++ stream

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
treenode的用法
treenode的用法

​在计算机编程领域,TreeNode是一种常见的数据结构,通常用于构建树形结构。在不同的编程语言中,TreeNode可能有不同的实现方式和用法,通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

2023.12.01

2981

7

C++ 高效算法与数据结构
C++ 高效算法与数据结构

本专题讲解 C++ 中常用算法与数据结构的实现与优化,涵盖排序算法(快速排序、归并排序)、查找算法、图算法、动态规划、贪心算法等,并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构(链表、树、堆、哈希表等),帮助开发者提升 在复杂应用中的算法设计与性能优化能力。

2025.12.22

416

20

深入理解算法:高效算法与数据结构专题
深入理解算法:高效算法与数据结构专题

本专题专注于算法与数据结构的核心概念,适合想深入理解并提升编程能力的开发者。专题内容包括常见数据结构的实现与应用,如数组、链表、栈、队列、哈希表、树、图等;以及高效的排序算法、搜索算法、动态规划等经典算法。通过详细的讲解与复杂度分析,帮助开发者不仅能熟练运用这些基础知识,还能在实际编程中优化性能,提高代码的执行效率。本专题适合准备面试的开发者,也适合希望提高算法思维的编程爱好者。

2026.01.06

437

22

C++ 数据结构与算法实现教程合集
C++ 数据结构与算法实现教程合集

以 C++ 为实现语言,系统讲解核心数据结构与算法,涵盖链表(单链表/双链表/环检测)、栈与队列(单调栈/优先队列)、二叉树(遍历/BST/AVL/红黑树)、哈希表(开地址法/链地址法)、图(邻接表/BFS/DFS/Dijkstra/拓扑排序)、常见排序算法(快排/归并/堆排/计数排序)的实现与复杂度分析,同时分享 LeetCode 刷题技巧、竞赛编程常用模板(二分/前缀和/滑动窗口/动态规划),帮助开发者夯实算法基础。

2026.05.09

512

25

GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

2026.11.17

0

15

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.17

0

15

GoFrame框架零基础入门
GoFrame框架零基础入门

本专题整理GoFrame框架的入门知识,从模块化设计理念、环境准备到跑通第一个Web服务,讲清目录分层、配置加载、日志与中间件的用法,并对比Gin、Go-Zero的差异,帮助Go开发者建立整体认知。

2026.11.17

0

15

SQLAlchemy 一对多关系怎么建立
SQLAlchemy 一对多关系怎么建立

SQLAlchemy 一对多关系怎么建立?本专题整理父子表外键、relationship 双向映射、关联查询、级联删除和加载优化等相关文章,帮助你理解并实现常见的 ORM 关系建模。

2026.11.17

0

10

SQLAlchemy 如何增删改查
SQLAlchemy 如何增删改查

SQLAlchemy 如何增删改查?本专题整理 ORM 新增记录、条件查询、更新和删除、Session 事务提交与批量处理等实用文章,帮助你掌握 Python 数据库操作流程。

2026.11.17

0

11

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
WebSocket手册
WebSocket手册

共0课时 | 0人学习

HTML5/CSS3/JavaScript/ES6入门课程
HTML5/CSS3/JavaScript/ES6入门课程

共102课时 | 11.2万人学习

前端基础到实战(HTML5+CSS3+ES6+NPM)
前端基础到实战(HTML5+CSS3+ES6+NPM)

共162课时 | 29.2万人学习