数据结构与算法——跳跃表

发布时间:2026/11/19 8:25:47

数据结构与算法——跳跃表 文章目录一、跳跃表概述二、跳跃表算法实现一、跳跃表概述跳跃表Skip List是一种概率性数据结构它就像是升级版的有序链表专门用来实现有序集合的功能。它通过引入多层索引来提高查找、插入和删除操作的效率使得这些操作的时间复杂度可以达到 O(log⁡n)其效率可以与平衡二叉搜索树相媲美。跳跃表的核心思想是通过随机化来维护多层索引从而避免像平衡树那样复杂的平衡操作。随机性决定节点层数在跳跃表中每个节点的层数是随机确定的。当插入一个新节点时算法会根据一个随机过程来决定该节点应该拥有多少层。通常这个随机过程基于抛硬币的思想比如抛一次硬币正面则该节点的层数加 1继续抛硬币直到出现反面为止。这种随机性使得跳跃表在构建时不需要预先知道数据集的大小和分布它会在动态插入和删除元素的过程中自动调整结构。平均性能而非最坏性能保证跳跃表通过随机化的方式来平衡其结构从而在平均情况下达到较好的性能。虽然在最坏情况下跳跃表的性能可能会退化为普通链表的性能例如所有节点的层数都为 1但这种情况发生的概率非常低。它的平均时间复杂度为 O(logn)这里的平均是基于随机算法的期望性能而不是对所有可能输入都能保证的最坏情况性能。有序性跳跃表中的元素是按照键值有序排列的。就像有序链表一样每个节点都有一个键可以理解为元素的值并且所有节点的键是按照从小到大或自定义的顺序排列的。这种有序性使得跳跃表可以高效地支持范围查询等操作例如查找某个范围内的所有元素。支持多种操作跳跃表可以实现有序集合所需的基本操作如插入、删除和查找。插入操作新元素会按照其键值的大小插入到合适的位置并且根据随机过程确定该元素节点的层数。删除操作先找到要删除的节点然后调整指针将其从跳跃表中移除同时保持跳跃表的有序性。查找操作利用跳跃表的多层结构查找过程可以通过高层指针快速跳过大量节点从而减少查找所需的比较次数提高查找效率。1.1 节点结构跳跃表是在有序链表的基础上发展而来的。为了提高链表的查找效率跳跃表会随机地为每个节点增加额外的指针这些指针可以跳过一些中间节点从而加快查找速度。每个节点可以有不同的层次层次越高该节点的指针可以跳过的节点数就越多。跳跃表的每个节点包含以下信息key键用于标识和排序元素的唯一标识。在插入新节点时会根据 key 的大小将节点插入到合适的位置以保证跳跃表的有序性。在搜索操作中也是根据 key 来确定要查找的元素位置。通常要求 key 是唯一的即跳跃表中不会存在两个 key 相同的节点。这样可以确保在搜索时能够准确地定位到一个节点。value值value 是与 key 关联的数据它存储了用户真正需要的数据信息。value 的类型可以根据具体需求进行定义比如整数、字符串、自定义对象等。当通过 key 找到对应的节点后就可以获取该节点的 value。层数当前节点所在的层数。指针数组它存储了该节点在不同层次上的后继节点的指针class SkipListNode { public: int key; int value; int level; SkipListNode** forward; SkipListNode(int key, int value, int level) : key(key), value(value), level(level) { forward new SkipListNode * [level 1]; for (int i 0; i level; i) { forward[i] nullptr; } } ~SkipListNode() { delete[] forward; } };1.2 层数跳跃表是一种分层的数据结构由多个有序链表组成其中高层链表是底层链表的子集。每一层的链表都是有序的且高层链表的节点间隔更大这使得在查找元素时可以通过高层链表快速跳过大量节点从而提高查找效率。在跳跃表中每个节点的 forward 数组记录的是该节点在不同层级链表上向前指向的后继节点。可以把跳跃表想象成一条道路每个节点沿着道路向前移动forward 数组就像是指引前进方向的路标告诉我们从当前节点向前可以到达哪些后续节点。forward[i] 表示该节点在第 i 层的后继节点指针。我们使用下面这个层数为 3 的跳跃表示例来为大家讲解一下当前节点和它的 forward 数组的关系第 2 层: 1 ---------------- 5 ----------- 8 - nullptr第 1 层: 1 ------ 3 ------ 5 ------ 7-- 8 - nullptr第 0 层: 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - nullptr对于跳跃表中第 1 个节点的 forward 数组的分析forward[0]在第 0 层节点 1 的下一个节点也是 2所以 forward[0] 同样指向节点 2。forward[1]在第 1 层节点 1 的下一个节点是 3所以 forward[1] 指向节点 3。可以想象成在第二层的快速路上从节点 1 直接跳到了节点 3。forward[2]在第 2 层节点 1 的下一个节点是 5所以 forward[2] 指向节点 5。这就像在最高层的超级快速路上从节点 1 一下子跨越到了节点 5。对于跳跃表中第 3 个节点的 forward 数组的分析forward[0]在第 0 层节点 3 的下一个节点是 4所以 forward[0] 指向节点 4。forward[1]在第 1 层节点 3 的下一个节点是 5所以 forward[1] 指向节点 5。forward[2]由于节点 3 没有出现在第 2 层那么在代码中通常会将 forward[2] 设为 nullptr表示在这一层没有后继节点。1.3 随机化层数每个节点的层数是随机生成的通常需要保证高层的节点数量逐渐减少。例如第 i层的节点数量大约是第 i−1层的一半。伯努利分布是一种离散概率分布它描述了只有两种可能结果的随机试验通常标记为成功取值为 1和失败取值为 0。在伯努利试验中每次试验成功的概率为 p失败的概率为 1 - p。std::bernoulli_distribution 是 C 标准库 random 头文件中提供的一个随机数分布类用于生成服从伯努利分布的随机布尔值。#include iostream #include random int main() { // 创建一个随机数引擎 std::random_device rd; std::mt19937 gen(rd()); // 创建一个伯努利分布对象成功概率为 0.7 std::bernoulli_distribution d(0.7); // 进行 10 次随机试验 for (int i 0; i 10; i) { bool result d(gen); std::cout (result ? Success : Failure) std::endl; } return 0; }二、跳跃表算法实现2.1 跳跃表定义class SkipList { public: SkipList(); ~SkipList(); SkipListNode* search(int key, std::functionvoid(int, SkipListNode*) updateFunc nullptr); void insert(int key, int value); bool remove(int key); void traverse(); private: int randomLevel(); void saveNode(int pos, SkipListNode* node, SkipListNode** update); private: SkipListNode* m_head; int m_level; std::mt19937 m_gen; std::bernoulli_distribution m_dist; static const int MAX_LEVEL 16; };2.2 数据查找构造函数和析构函数SkipList::SkipList() : m_level(0), m_head(new SkipListNode(-1, -1, MAX_LEVEL)) { // 初始化随机数种子 random_device dev; m_gen.seed(dev()); } SkipList::~SkipList() { SkipListNode* current m_head; while (current ! nullptr) { SkipListNode* next current-forward[0]; cout 释放节点值: current-value endl; delete current; current next; } }查找算法SkipListNode* SkipList::search(int key, functionvoid(int, SkipListNode*) updateFunc) { SkipListNode* current m_head; for (int i m_level; i 0; --i) { while (current-forward[i] ! nullptr current-forward[i]-key key) { current current-forward[i]; } if (updateFunc) { updateFunc(i, current); } } current current-forward[0]; if (current ! nullptr current-key key) { return current; } return nullptr; }2.3 数据添加int SkipList::randomLevel() { int level 1; while (m_dist(m_gen) level MAX_LEVEL) { level; } return level; } void SkipList::insert(int key, int value) { // update 数组用于记录在每一层需要更新的节点 SkipListNode* update[MAX_LEVEL1]; auto func bind(SkipList::saveNode, this, placeholders::_1, placeholders::_2, update); SkipListNode* current search(key, func); if (current ! nullptr) { current-value value; } else { int newLevel randomLevel(); if (newLevel m_level 1) { newLevel m_level 1; } if (newLevel m_level) { update[newLevel] m_head; m_level newLevel; } SkipListNode* newNode new SkipListNode(key, value, newLevel); for (int i 0; i newLevel; i) { newNode-forward[i] update[i]-forward[i]; update[i]-forward[i] newNode; } } }2.4 数据删除bool SkipList::remove(int key) { SkipListNode* update[MAX_LEVEL1]; auto func bind(SkipList::saveNode, this, placeholders::_1, placeholders::_2, update); SkipListNode* current search(key, func); if (current ! nullptr) { for (int i 0; i current-level; i) { update[i]-forward[i] current-forward[i]; } delete current; while (m_level 0 m_head-forward[m_level] nullptr) { m_level--; } return true; } return false; }
延伸阅读

更多相关文章

2026/11/17 2:57:17

高精度通用时间测量频率计模块设计与等精度测量方案解析

频率计这活儿,听起来简单——不就是数脉冲吗?真做起来,采样率、时基、触发、校准这些细节摞在一起,就变成一个让人头疼的“高精度通用时间测量”工程。我最近刚把一个频率计模块方案从需求定型到硬件落地完整跑了一遍,…

2026/11/17 6:23:54

AI编程实战:RS485与LoRa设备参数调试工具快速开发

上个月我在仓库里蹲了一下午,干了一件特别无语的事:给一箱带LoRa模块的采集终端挨个配频点和发射功率,旁边还躺着一台RS485电表等着改互感器倍率。手边只有一个串口助手和一本写满寄存器地址的PDF手册,一条条AT指令敲过去&#xf…

2026/11/19 8:21:43

低压电工证起什么作用?郑州报考避坑指南全解析

低压电工证起什么作用?郑州报考避坑指南全解析 你是不是也遇到过这种情况?想考低压电工证,但不知道去哪儿报名,怕被中介坑,怕花冤枉钱,怕考试不过白费时间?别急,这篇文章就是为了解决这些问题,尤其是 郑州本地从业者…

2026/11/19 8:21:43

初级电工证啥也不戴报名费多少钱良心建议

初级电工证啥也不戴报名费多少钱良心建议 你是不是正在为 初级电工证啥也不戴 的事情发愁?怕被中间人坑,又不知道去哪儿报名?别急,今天给你一个 良心建议 ,让你少走弯路,省下冤枉钱。 初级电工证啥也不戴,报考门槛到底多低?…

2026/11/19 8:21:43

电工证考试时间7月到期换证流程 上岗必备

电工证考试时间7月到期换证流程 上岗必备 工地太忙根本没时间复习考试,这话我听着都心疼。我之前在河南某建筑工地带过一个新手电工,天天忙得脚不沾地,连晚上都得加班,结果电工证到期了,他一点准备都没有,最后只能临时抱佛脚,差点耽误了整个项目进度…

2026/11/19 8:21:43

电工证成绩结果查询怎么查?内部消息告诉你怎么避开复审陷阱

电工证成绩结果查询怎么查?内部消息告诉你怎么避开复审陷阱 证书过期了不知道怎么复审延期,这事儿我见过太多了。特别是安阳公路工程的从业者,很多人以为电工证考了就完事儿,结果几年后突然发现证书到期了,这时候再找补已经来不及了。其实, 内部消息…

2026/11/19 8:16:43

_中级电工证有用吗培训机构怎么选

中级电工证有用吗 郑州报考避坑指南 你是不是也在担心,自己学历不高,连中级电工证都报不了?其实, 中级电工证对很多人来说都是翻身的跳板…

2026/11/18 21:12:58

电工证考试口诉怎么准备值不值得考

电工证考试口诉怎么准备值不值得考 实操考试心里没底怕挂科,这是大多数准备考电工证的人心里最真实的感受。尤其是面对【电工证考试口诉】环节,很多人不知道该怎么准备,甚至担心自己说不好就被淘汰。其实,只要掌握方法, 值不值得考…

2026/11/18 21:55:23

桑植县考电工证千万别踩坑!报名全流程教你避坑

桑植县考电工证千万别踩坑!报名全流程教你避坑 你是不是也遇到过这种情况:想考个电工证,但不知道从哪儿下手,怕被中介坑,怕花冤枉钱,更怕考了证还不能用?别急,这正是你该看这篇文章的原因。在桑植县考电工证,确实有很多人被坑过,但只要你知道流程、…

2026/11/19 0:04:42

深圳电工证培训考场模拟考试题库:郑州报考避坑指南

深圳电工证培训考场模拟考试题库:郑州报考避坑指南 证书过期了不知道怎么复审延期,很多人在遇到这个问题的时候才意识到特种作业证的重要性。其实,不管是电工证、焊工证还是高处作业证,这些证书不仅是上岗的“通行证”,更是法律对安全操作的硬性要求。尤…

2026/11/19 0:04:42

天津电工证查询入口多少钱能报上名

天津电工证查询入口多少钱能报上名 学历不高怕报不上名?别急,天津电工证查询入口其实没你想的那么难。今天咱们就来聊聊,怎么用最低的门槛、最少的钱,把电工证拿下来,还能查得到、用得上。 电工证到底值不值?先搞清楚它的作用…

2026/11/18 12:37:05

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

在智慧养宠时代,基于视觉的宠物身份识别技术正逐步从实验室走向家庭应用。然而,与配合度高的人类不同,宠物是典型的“非合作生物识别对象”——它们不会主动配合摄像头调整姿态,更无法控制光照环境。实际应用中,我们常…

2026/11/18 1:15:04

SSM电子书店源码全解析:结构、原理、部署与排错实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

还想了解更多?直接咨询顾问

免费诊断 + 免费方案 + 透明报价。

全国咨询热线400-8866-253
免费获取方案
☎咨询二维码 ☎ ↑