1. 跳跃表基本概念

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

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

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

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

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

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

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

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

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

1.1 节点结构

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

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

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

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

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

  • value 的类型可以根据具体需求进行定义，比如整数、字符串、自定义对象等。
  • 当通过 key 找到对应的节点后，就可以获取该节点的 value。

• 层数：当前节点所在的层数。

• 指针数组：它存储了该节点在不同层次上的后继节点的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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 数组的关系：

1
2
3

第 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[1] 同样指向节点 2。
• forward[1]：在第 1 层，节点 1 的下一个节点是 3，所以 forward[2] 指向节点 3。可以想象成在第二层的快速路上，从节点 1 直接跳到了节点 3。
• forward[2]：在第 2 层，节点 1 的下一个节点是 5，所以 forward[3] 指向节点 5。这就像在最高层的超级快速路上，从节点 1 一下子跨越到了节点 5。

对于跳跃表中第 3 个节点的 forward 数组的分析

• forward[0]：在第 0 层，节点 3 的下一个节点是 4，所以 forward[1] 指向节点 4。
• forward[1]：在第 1 层，节点 3 的下一个节点是 5，所以 forward[2] 指向节点 5。
• forward[2]：由于节点 3 没有出现在第 2 层，那么在代码中通常会将 forward[3] 设为 nullptr，表示在这一层没有后继节点。

1.3 随机化层数

每个节点的层数是随机生成的，通常需要保证高层的节点数量逐渐减少。例如，第 i层的节点数量大约是第 i−1层的一半。

伯努利分布是一种离散概率分布，它描述了只有两种可能结果的随机试验，通常标记为成功（取值为 1）和失败（取值为 0）。在伯努利试验中，每次试验成功的概率为 p，失败的概率为 1 - p。std::bernoulli_distribution 是 C++ 标准库 <random> 头文件中提供的一个随机数分布类，用于生成服从伯努利分布的随机布尔值。

1
2

// 构造函数
explicit bernoulli_distribution( double p = 0.5 );

• 参数p 是成功的概率，取值范围是 [0, 1]，默认值为 0.5。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#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;
}

• 随机数引擎：std::random_device 用于生成随机种子，std::mt19937 是一个常用的随机数生成器，使用 std::random_device 生成的种子进行初始化。
• 伯努利分布对象：std::bernoulli_distribution d(0.7) 创建了一个成功概率为 0.7 的伯努利分布对象。
• 随机试验：通过调用 d(gen) 进行随机试验，返回一个布尔值，表示试验的结果。

2. 跳跃表定义

定义好了跳跃表节点之后，就可以把跳跃表的类定义出来了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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.1 公共成员函数

1. 构造函数 SkipList()
   • 作用：用于创建一个新的跳跃表对象。在构造函数中，通常会对跳跃表的头节点、初始层数等进行初始化操作。
2. 析构函数 ~SkipList()
   • 作用：在跳跃表对象销毁时被调用，负责释放跳跃表所占用的内存，例如删除所有节点。
3. 查找函数 SkipListNode* search(int key, std::function<void(int, SkipListNode*)> updateFunc = nullptr)
   • 参数：
     • key：要查找的键值。
     • updateFunc：一个可选的函数对象，默认为 nullptr。该函数可以在查找过程中对节点进行额外的操作（在插入数据的时候需要记录查找路径）。
   • 返回值：如果找到键值为 key 的节点，则返回该节点的指针；否则返回 nullptr。
4. 插入函数 void insert(int key, int value)
   • 参数：
     • key：要插入的键值。
     • value：与键值关联的值。
   • 作用：将键值对 (key, value) 插入到跳跃表中。插入过程中可能需要调整跳跃表的层数和节点指针。
5. 删除函数 bool remove(int key)
   • 参数：key：要删除的键值。
   • 返回值：如果成功删除键值为 key 的节点，则返回 true；否则返回 false。
6. 遍历函数 void traverse()
   • 作用：遍历跳跃表中的所有节点，并输出节点的键值和相关信息。

2.2 私有成员函数

1. 随机层数生成函数 int randomLevel()
   • 作用：为新插入的节点随机生成一个层数。跳跃表的每个节点的层数是随机确定的，通常使用抛硬币的方式（伯努利分布）来决定是否要增加节点的层数。
2. 保存节点位置函数 void SkipList::saveNode(int pos, SkipListNode* node, SkipListNode** update)
   • 作用：在查找目标节点的过程里，把每一层上最后一个键小于目标键的节点记录下来，这些记录会被后续的插入、删除等操作所使用。
   • 参数：
     • pos：代表当前所在的层。在跳跃表中，不同的层有着不同的索引级别，pos 用于标识具体是哪一层。
     • node：是一个指向 SkipListNode 类型节点的指针，该节点就是当前层上最后一个键小于目标键的节点。
     • update：这是一个二级指针，指向一个 SkipListNode* 类型的数组。这个数组会存储每一层上最后一个键小于目标键的节点的指针。

2.3 私有成员变量

1. 头节点指针 SkipListNode* m_head

   指向跳跃表的头节点。头节点是一个特殊的节点，它不存储实际的键值对，主要用于方便操作跳跃表的第一层和更高层。

2. 当前最大层数 int m_level

   记录跳跃表当前的最大层数。跳跃表的层数会随着插入和删除操作而动态变化。

3. 随机数生成器 std::mt19937 m_gen

   用于生成高质量的随机数。std::mt19937 是 C++ 标准库中的梅森旋转算法随机数生成器，它可以生成均匀分布的随机数。

4. 伯努利分布对象 std::bernoulli_distribution m_dist

   用于模拟抛硬币的过程，决定新插入节点的层数是否要增加。伯努利分布是一种离散概率分布，只有两个可能的结果（成功或失败），通常用于模拟二选一的随机事件。

5. 最大层数常量 static const int MAX_LEVEL = 16

   定义跳跃表的最大层数。为了避免跳跃表的层数过高导致性能下降，通常会设置一个最大层数限制。

3. 数据查找

3.1 构造和析构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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;
    }
}

3.2 查找

跳跃表由多个节点组成，每个节点包含键（Key）、值（Value）以及多个指向后续节点的指针，这些指针对应不同的层级。跳跃表有一个头节点（Head Node），它位于最高层，包含指向各层第一个节点的指针。

在跳跃表中查找数据的过程如下：

1. 初始化：从跳跃表的头节点开始，让当前指针（辅助指针）指向该头结点。

2. 逐层查找：从最高层开始，沿着当前层的指针进行查找，比较当前节点的键与目标键。

   • 如果当前节点的下一个节点不为空，且下一个节点的键小于目标键，则将当前指针移动到下一个节点。

   • 如果下一个节点的键等于目标键，则表示找到了目标节点，查找过程结束。

   • 如果下一个节点的键大于目标键，或者下一个节点为空，则说明在当前层找不到目标键，需要向下移动一层。

3. 向下移动一层

   当在某一层无法继续前进（即下一个节点的键大于目标键或为空）时，将当前指针移动到当前节点在下层的指针，然后继续在该层进行查找。

4. 重复步骤 2 和 3：不断重复步骤 2 和 3，直到找到目标键或者到达最底层且无法继续前进。

5. 判断查找结果

   • 如果在某一层找到了键等于目标键的节点，则返回该节点的值，查找成功。

   • 如果到达最底层且当前指针的下一个节点为空，或者下一个节点的键大于目标键，则说明目标键不存在于跳跃表中，查找失败。

根据上述流程对应的示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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;
}

4. 数据添加

在跳跃表中添加新节点的步骤如下：

1. 确定新节点的层数

   在插入新节点之前，需要先确定该节点的层数。通常使用随机算法来决定新节点的层数，例如通过抛硬币的方式，以一定的概率决定是否继续增加层数，直到达到最大层数或者抛硬币结果为反面。

2. 查找插入位置

   从跳跃表的头节点开始，从最高层的指针开始查找。沿着当前层的指针进行查找，直到找到第一个键大于或等于新节点键的节点。在查找过程中，记录下每一层最后一个键小于新节点键的节点，这些节点将用于后续的插入操作。

3. 更新跳跃表的最大层数

   如果新节点的层数大于当前跳跃表的最大层数，则需要更新跳跃表的最大层数，并更新头节点的指针。

4. 插入新节点

   创建新节点，并将其插入到每一层中。具体操作是，将新节点的指针插入到记录的每一层最后一个键小于新节点键的节点之后。

根据上面的描述，跳跃表中添加数据对应的示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

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;
        }
    }
}

4.1 update 数组的作用

在跳跃表中插入一个新节点时，需要从最高层开始，逐层向下查找合适的插入位置。对于每一层，我们要找到该层中小于待插入键值 key 的最大节点，这个节点就是在该层插入新节点时需要更新 forward 指针的节点。update 数组用于记录每一层这样的节点。

假设我们有一个跳跃表，结构如下：

1
2
3

第 2 层:  HEAD -> 1 ----------------> 5 -----------> 8
第 1 层:  HEAD -> 1 ------> 3 ------> 5 ------> 7 -> 8
第 0 层:  HEAD -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

现在要插入键值为 4 的节点。

• 第 2 层（i = 2）：

  • 从跳跃表的头节点开始，current 指向头节点。
  • 头节点的 forward[2] 指向节点 1，1 < 4，所以 current 移动到节点 1。
  • 节点 1 的 forward[2] 指向节点 5，5 > 4，while 循环结束。
  • update[2] 记录为节点 1。

• 第 1 层（i = 1）：

  • current 从节点 1 开始。
  • 节点 1 的 forward[1] 指向节点 3，3 < 4，current 移动到节点 3。
  • 节点 3 的 forward[1] 指向节点 5，5 > 4，while 循环结束。
  • update[1] 记录为节点 3。

• 第 0 层（i = 0）：

  • current 从节点 3 开始。
  • 节点 3 的 forward[0] 指向节点 4，4 = 4（这里不满足 current->forward[0]->key < key），while 循环结束。
  • update[0] 记录为节点 3。

这样，update 数组就记录了每一层中在插入位置之前的节点，后续插入新节点时，就可以根据这些记录更新相应的 forward 指针。该过程对应的就是insert函数开头的这几行代码：

1
2
3

SkipListNode* update[MAX_LEVEL + 1];
auto func = bind(&SkipList::saveNode, this, placeholders::_1, placeholders::_2, update);
SkipListNode* current = search(key, func);

4.2 绑定回调函数

1

auto func = bind(&SkipList::saveNode, this, placeholders::_1, placeholders::_2, update);

• bind 是 C++ 标准库中的一个函数模板，用于将一个可调用对象（这里是 SkipList 类的成员函数 saveNode）与其参数进行绑定，生成一个新的可调用对象 func。
• &SkipList::saveNode：要绑定的成员函数的地址。
• this：表示当前 SkipList 对象的指针，因为成员函数需要通过对象来调用。
• placeholders::_1 和 placeholders::_2：占位符，用于表示在调用 func 时将传入的两个参数。
• update：将 update 数组作为参数传递给 saveNode 函数。

1

SkipListNode* current = search(key, func);

• 调用 search 函数，传入要查找的键 key 和绑定好的回调函数 func。search 函数会在跳跃表中查找键为 key 的节点，并在查找过程中调用 func 函数更新 update 数组。
• current 指向找到的节点，如果未找到则为 nullptr。

4.3 randomLevel 函数

SkipList::randomLevel() 函数的核心逻辑是使用一个伯努利分布（m_dist）来决定是否要增加当前节点的层数。在这个函数中：

• 初始时节点的层数 level 被设为 1。
• 每次循环都会调用 m_dist(m_gen) 生成一个布尔值，如果这个布尔值为 true ，并且当前层数 level 小于最大层数 MAX_LEVEL，则将 level 加 1。
• 当 m_dist(m_gen) 返回 false 或者 level 达到 MAX_LEVEL 时，循环结束，函数返回最终的 level。

由于伯努利分布生成 true 的概率（ p）是固定的，那么每增加一层，就需要再次通过这个伯努利试验的检验。也就是说，节点达到第 n 层的概率是达到第 n - 1 层的概率乘以 p。

假设 p = 0.5，MAX_LEVEL = 4，我们可以计算不同层数的概率：

• P(level = 1) = 1 - 0.5 = 0.5
• P(level = 2) = 0.5 * (1 - 0.5) = 0.25
• P(level = 3) = 0.5² * (1 - 0.5) = 0.125
• P(level = 4) = 0.5³ * (1 - 0.5) = 0.0625

5. 数据删除

在跳跃表中添加新节点的步骤如下：

1. 查找要删除的节点

   从跳跃表的头节点开始，从最高层的指针开始查找。沿着当前层的指针进行查找，直到找到第一个键大于或等于要删除节点键的节点。在查找过程中，记录下每一层最后一个键小于要删除节点键的节点，这些节点将用于后续的删除操作。

2. 检查节点是否存在

   如果找到的节点的键等于要删除的键，则表示该节点存在；否则，说明要删除的节点不存在，直接返回。

3. 更新指针

   从最底层开始，依次更新每一层的指针，将指向要删除节点的指针直接指向要删除节点的下一个节点。

4. 调整跳跃表的最大层数

   在删除节点后，可能会出现某些层只有头节点的情况。如果出现这种情况，需要调整跳跃表的最大层数，将这些只有头节点的层去掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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) 
        {
            if (update[i]->forward[i] != current) 
            {
                break;
            }
            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;
}

在跳跃表中，空层指的是某一层上没有除头节点之外的其他有效节点，即头节点在该层的前进指针指向 nullptr。当删除节点时，如果该节点是某一层上唯一的有效节点，删除后这一层就会变成空层。

当对跳跃表中的数据进行了若干次删除之后，再次进行某一个节点删除的时候，可能会导致跳跃表的若干层都是空层，所以需要通过循环将它们全部删掉。

1
2
3
4

while (m_level > 0 && m_head->forward[m_level] == nullptr) 
{
    m_level--;
}

• 检查跳跃表的最高层是否为空（即头节点在该层的前进指针指向 nullptr）。
• 如果最高层为空，则将跳跃表的最大层数 m_level 减 1，直到最高层不为空或 m_level 为 0。

6. 遍历和测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

void SkipList::traverse()
{
    SkipListNode* current = m_head->forward[0];
    while (current != nullptr) 
    {
        cout << "Key: " << current->key << ", Value: " << current->value << endl;
        current = current->forward[0];
    }
}

int main() 
{
    SkipList skipList;

    // 插入一些元素
    for (int i = 0; i < 10; ++i)
    {
        skipList.insert(i, i*100);   
    }

    // 遍历跳跃表
    cout << "遍历跳跃表:" << endl;
    skipList.traverse();

    // 查找元素
    SkipListNode* sk = skipList.search(2);
    if (sk) 
    {
        cout << "key=2, value: " << sk->value << endl;
    }
    else 
    {
        cout << "Key 2 not found." << endl;
    }

    // 删除元素
    if (skipList.remove(2)) 
    {
        cout << "Key 2 removed." << endl;
    }
    else
    {
        cout << "Key 2 not found for removal." << endl;
    }
    cout << "再次遍历跳跃表:" << endl;
    skipList.traverse();

    return 0;
}

终端打印的结果为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

遍历跳跃表:
Key: 0, Value: 0
Key: 1, Value: 100
Key: 2, Value: 200
Key: 3, Value: 300
Key: 4, Value: 400
Key: 5, Value: 500
Key: 6, Value: 600
Key: 7, Value: 700
Key: 8, Value: 800
Key: 9, Value: 900
key=2, value: 200
Key 2 removed.
再次遍历跳跃表:
Key: 0, Value: 0
Key: 1, Value: 100
Key: 3, Value: 300
Key: 4, Value: 400
Key: 5, Value: 500
Key: 6, Value: 600
Key: 7, Value: 700
Key: 8, Value: 800
Key: 9, Value: 900
释放节点值: -1
释放节点值: 0
释放节点值: 100
释放节点值: 300
释放节点值: 400
释放节点值: 500
释放节点值: 600
释放节点值: 700
释放节点值: 800
释放节点值: 900

7. 跳跃表和红黑树对比

跳跃表（Skip List）和红黑树（Red - Black Tree）都是用于实现有序集合的数据结构，它们在很多方面存在差异，以下从多个维度对二者进行对比：

1. 数据结构原理

   • 跳跃表：跳跃表是一种概率性数据结构，它基于有序链表扩展而来。通过为每个节点随机分配一个层数，每个节点不仅有指向下一个节点的指针，还有指向更高层节点的指针，从而可以在查找、插入和删除操作时跳过部分节点，提高操作效率。
   • 红黑树：红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色（红色或黑色）。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

2. 操作复杂度

   • 平均情况

     • 查找：跳跃表和红黑树的平均时间复杂度都是 O(log n) 。跳跃表通过随机层数的高层指针快速跳过部分节点；红黑树则通过平衡结构保证了查找路径不会过长。

     • 插入：二者平均时间复杂度同样为 O(log n) 。跳跃表插入时需要随机确定新节点的层数并调整指针；红黑树插入新节点后需要进行旋转和颜色调整来保持平衡。

     • 删除：平均时间复杂度也是 O(log n) 。跳跃表删除节点后要调整相关指针；红黑树删除节点后同样需要通过旋转和颜色调整来维持平衡。

   • 最坏情况

     • 跳跃表在最坏情况下（所有节点层数都为 1），查找、插入和删除操作的时间复杂度会退化为 O(n) ，不过这种情况发生的概率极低。
     • 红黑树在最坏情况下，查找、插入和删除操作的时间复杂度依然能保证为 O(log n) ，因为它是严格的平衡结构。

   3. 实现难度

      • 跳跃表

        实现相对简单，代码逻辑较为直观。主要的操作集中在节点的插入、删除时指针的调整，以及随机层数的生成，不需要复杂的旋转操作。

      • 红黑树

        实现难度较大，需要处理多种不同的插入和删除情况，并且要进行复杂的旋转和颜色调整操作来维持树的平衡。代码的调试和维护也相对困难。

   4. 并发性能

      • 跳跃表

        并发性能较好。由于其结构的特性，在并发环境下，不同线程可以同时对不同层的节点进行操作，加锁粒度可以较小，从而减少锁竞争，提高并发性能。例如在多线程环境下插入或删除元素时，只需要对涉及的部分节点加锁。

      • 红黑树

        并发性能相对较差。在进行插入、删除操作时，为了保证树的平衡，可能会涉及到大量节点的调整，需要对较多的节点加锁，锁竞争较为严重，不利于并发操作。

   5. 空间复杂度

      • 跳跃表

        空间复杂度通常为 O(n) ，但由于每个节点可能有多层指针，实际使用的额外空间会比理论值多一些。平均情况下，每个节点的指针数约为 2 个，但在极端情况下，空间开销可能会较大。

      • 红黑树

        空间复杂度也是 O(n) ，每个节点除了存储数据和左右子节点指针外，还需要一个额外的颜色位，整体空间开销相对稳定。

   6. 应用场景

      • 跳跃表

        适用于并发场景，如 Redis 中的有序集合就使用跳跃表实现，利用其较好的并发性能和简单的实现，在多线程环境下高效地处理数据。

      • 红黑树

        广泛应用于各种标准库中，如 Java 的 TreeMap 和 TreeSet，C++ 的 STL 中的 set 和 map 等。这些场景更注重最坏情况下的性能保证。