企业官网建设流程全解析

文章目录

• 一、跳跃表概述
• 二、跳跃表算法实现

一、跳跃表概述

跳跃表（Skip List）是一种概率性数据结构，它就像是升级版的有序链表，专门用来实现有序集合的功能。它通过引入多层索引来提高查找、插入和删除操作的效率，使得这些操作的时间复杂度可以达到 O(log⁡n)，其效率可以与平衡二叉搜索树相媲美。跳跃表的核心思想是通过随机化来维护多层索引，从而避免像平衡树那样复杂的平衡操作。

• 随机性决定节点层数：在跳跃表中，每个节点的层数是随机确定的。

当插入一个新节点时，算法会根据一个随机过程来决定该节点应该拥有多少层。通常，这个随机过程基于抛硬币的思想，比如抛一次硬币，正面则该节点的层数加 1，继续抛硬币，直到出现反面为止。这种随机性使得跳跃表在构建时不需要预先知道数据集的大小和分布，它会在动态插入和删除元素的过程中自动调整结构。

• 平均性能而非最坏性能保证：跳跃表通过随机化的方式来平衡其结构，从而在平均情况下达到较好的性能。

虽然在最坏情况下，跳跃表的性能可能会退化为普通链表的性能（例如所有节点的层数都为 1），但这种情况发生的概率非常低。它的平均时间复杂度为 O(logn)，这里的平均是基于随机算法的期望性能，而不是对所有可能输入都能保证的最坏情况性能。

• 有序性：跳跃表中的元素是按照键值有序排列的。

就像有序链表一样，每个节点都有一个键（可以理解为元素的值），并且所有节点的键是按照从小到大（或自定义的顺序）排列的。这种有序性使得跳跃表可以高效地支持范围查询等操作，例如查找某个范围内的所有元素。

• 支持多种操作：跳跃表可以实现有序集合所需的基本操作，如插入、删除和查找。

1. 插入操作：新元素会按照其键值的大小插入到合适的位置，并且根据随机过程确定该元素节点的层数。
2. 删除操作：先找到要删除的节点，然后调整指针将其从跳跃表中移除，同时保持跳跃表的有序性。
3. 查找操作：利用跳跃表的多层结构，查找过程可以通过高层指针快速跳过大量节点，从而减少查找所需的比较次数，提高查找效率。

1.1 节点结构

跳跃表是在有序链表的基础上发展而来的。为了提高链表的查找效率，跳跃表会随机地为每个节点增加额外的指针，这些指针可以跳过一些中间节点，从而加快查找速度。每个节点可以有不同的层次，层次越高，该节点的指针可以跳过的节点数就越多。

跳跃表的每个节点包含以下信息：

• key（键）：用于标识和排序元素的唯一标识。

1. 在插入新节点时，会根据 key 的大小将节点插入到合适的位置，以保证跳跃表的有序性。在搜索操作中，也是根据 key 来确定要查找的元素位置。
2. 通常要求 key 是唯一的，即跳跃表中不会存在两个 key 相同的节点。这样可以确保在搜索时能够准确地定位到一个节点。

• value（值）：value 是与 key 关联的数据，它存储了用户真正需要的数据信息。

1. value 的类型可以根据具体需求进行定义，比如整数、字符串、自定义对象等。
2. 当通过 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::function<void(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, function<void(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_LEVEL+1]; 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_LEVEL+1]; 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; }