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

文章目录一、跳跃表概述二、跳跃表算法实现一、跳跃表概述跳跃表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; }