everystep

1206. 设计跳表

跳表存在的场景还是蛮多了，例如 Redis 和 LevelDB 中都有跳表，面试的时候被问到的频率不低。看完下面的内容就能写这道题了：力扣 1206. 设计跳表 https://leetcode.cn/problems/design-skiplist/description/

跳表是一种数据结构，可以被看作是对标准链表的一种改进，使得查找数据的速度变得更快。

接下来会逐层展示跳表的遍历过程，并在每一层都画出相应的图。下面的例子跳表有 4 层，存储的整数值如下，目标值 target = 50。

初始跳表

跳表在链表的基础上增加了多层额外的链表，每一层都跳过一些元素，从而加快搜索速度。

Level 3:  Head -> 11 -------------------------------------------> 33 -------------------------------------------> 55 -> NULL
Level 2:  Head -> 11 -------------------> 22 -------------------> 33 -------------------> 44 -------------------> 55 -------------------> 66 -> NULL
Level 1:  Head -> 11 -------> 15 -------> 22 -------> 27 -------> 33 -------> 37 -------> 44 -------> 48 -------> 55 -------> 59 -------> 66 -------> 72 -> NULL
Level 0:  Head -> 11 -> 13 -> 15 -> 18 -> 22 -> 24 -> 27 -> 30 -> 33 -> 35 -> 37 -> 40 -> 44 -> 46 -> 48 -> 51 -> 55 -> 57 -> 59 -> 61 -> 66 -> 69 -> 72 -> 75 -> NULL

• Level 0 是原始链表，包含所有元素。
• Level 1 是第二层，它跳过了一些元素（例如，它可能只包含每两个元素中的一个）。
• Level 3 是顶层，跳过更多的元素（例如，它可能只包含每四个元素中的一个）。

当进行搜索时，你会从最顶层开始，这允许你跳过大部分元素。一旦你到达了需要下降到更低层继续搜索的点，就向下移动一层，再继续搜索。这个过程一直持续到找到目标元素或到达最底层链表。

这种结构使得跳表在查找元素时比普通链表更加高效，因为它减少了需要遍历的节点数量。同时，跳表在插入和删除操作时也保持了较高的效率，因为只需更新相对较少的链接。

遍历 Level 3

• p 从 Head 开始。
• p 移动到 11 -> 33。
• p 到达 55，停止（因为 55 > 50）。pre[3] = 33。

Level 3:  Head -> 11 -------------------------------------------> 33 (pre[3]) ----------------------------------> 55 -> NULL
Level 2:  Head -> 11 -------------------> 22 -------------------> 33 -------------------> 44 -------------------> 55 -------------------> 66 -> NULL
Level 1:  Head -> 11 -------> 15 -------> 22 -------> 27 -------> 33 -------> 37 -------> 44 -------> 48 -------> 55 -------> 59 -------> 66 -------> 72 -> NULL
Level 0:  Head -> 11 -> 13 -> 15 -> 18 -> 22 -> 24 -> 27 -> 30 -> 33 -> 35 -> 37 -> 40 -> 44 -> 46 -> 48 -> 51 -> 55 -> 57 -> 59 -> 61 -> 66 -> 69 -> 72 -> 75 -> NULL

遍历 Level 2

• p 继续从 33 开始。
• p 移动到 44。
• p 到达 55，停止（因为 55 > 50）。pre[2] = 44。

Level 3:  Head -> 11 -------------------------------------------> 33 -------------------------------------------> 55 -> NULL
Level 2:  Head -> 11 -------------------> 22 -------------------> 33 -------------------> 44 (pre[2]) ----------> 55 -------------------> 66 -> NULL
Level 1:  Head -> 11 -------> 15 -------> 22 -------> 27 -------> 33 -------> 37 -------> 44 -------> 48 -------> 55 -------> 59 -------> 66 -------> 72 -> NULL
Level 0:  Head -> 11 -> 13 -> 15 -> 18 -> 22 -> 24 -> 27 -> 30 -> 33 -> 35 -> 37 -> 40 -> 44 -> 46 -> 48 -> 51 -> 55 -> 57 -> 59 -> 61 -> 66 -> 69 -> 72 -> 75 -> NULL

遍历 Level 1

• p 从 44 开始。
• p 移动到 48。
• p 到达 55，停止（因为 55 > 50）。pre[1] = 48。

Level 3:  Head -> 11 -------------------------------------------> 33 ----------------------------------------------> 55 -> NULL
Level 2:  Head -> 11 -------------------> 22 -------------------> 33 -------------------> 44 ----------------------> 55 ----------------> 66 -> NULL
Level 1:  Head -> 11 -------> 15 -------> 22 -------> 27 -------> 33 -------> 37 -------> 44 -------> 48 (pre[1]) -> 55 ---> 59 --------> 66 -------> 72 -> NULL
Level 0:  Head -> 11 -> 13 -> 15 -> 18 -> 22 -> 24 -> 27 -> 30 -> 33 -> 35 -> 37 -> 40 -> 44 -> 46 -> 48 -> 51 -> 55 -> 57 -> 59 -> 61 -> 66 -> 69 -> 72 -> 75 -> NULL

遍历 Level 0

• p 从 48 开始。
• p 到达 51，停止（因为 51 > 50）。pre[0] = 48。

Level 3:  Head -> 11 -------------------------------------------> 33 ----------------------------------------------------> 55 -> NULL
Level 2:  Head -> 11 -------------------> 22 -------------------> 33 -------------------> 44 ----------------------------> 55 ----------------> 66 -> NULL
Level 1:  Head -> 11 -------> 15 -------> 22 -------> 27 -------> 33 -------> 37 -------> 44 -------> 48 ----------------> 55 -------> 59 ----> 66 -------> 72 -> NULL
Level 0:  Head -> 11 -> 13 -> 15 -> 18 -> 22 -> 24 -> 27 -> 30 -> 33 -> 35 -> 37 -> 40 -> 44 -> 46 -> 48 (pre[0]) -> 51 -> 55 -> 57 -> 59 -> 61 -> 66 -> 69 -> 72 -> 75 -> NULL

结果

最终 pre 数组中的节点如下，这些节点表示在每个层级中最后一个小于 50 的节点：

• pre[3] = 节点 33
• pre[2] = 节点 44
• pre[1] = 节点 48
• pre[0] = 节点 48

在这个过程中，我们可以看到 find 函数是如何在每个层级中逐步靠近目标值的位置，从而高效地定位目标值可能存在的地方。

数据结构设计

    // 跳表节点的结构定义
    struct Node {
        int val; // 节点存储的值
        vector<Node*> next; // 存储到下一个节点的指针数组，next[i] 表示当前节点在第 i 层的下一个节点

        Node(int _val) : val(_val) { // 构造函数，初始化节点值和 next 数组
            next.resize(level, NULL); // 将 next 数组的大小初始化为 level，并全部指向 NULL
        }
    }*head; // 跳表的头节点，初始化时指向一个虚拟节点

find

结合一个具体的例子讲解 find 函数，我们假设目标值 (target) 是 36。我们的目标是找到跳表中每个层级上小于 36 的最大节点。以下是跳表的当前状态和 find 函数的执行步骤。

跳表当前状态:

Level 3:  Head -> 11 -------------------------------------------> 33 -------------------------------------------> 55 -> NULL
Level 2:  Head -> 11 -------------------> 22 -------------------> 33 -------------------> 44 -------------------> 55 -------------------> 66 -> NULL
Level 1:  Head -> 11 -------> 15 -------> 22 -------> 27 -------> 33 -------> 37 -------> 44 -------> 48 -------> 55 -------> 59 -------> 66 -------> 72 -> NULL
Level 0:  Head -> 11 -> 13 -> 15 -> 18 -> 22 -> 24 -> 27 -> 30 -> 33 -> 35 -> 37 -> 40 -> 44 -> 46 -> 48 -> 51 -> 55 -> 57 -> 59 -> 61 -> 66 -> 69 -> 72 -> 75 -> NULL

执行 find(36, p) 的步骤:

1. 开始于 Level 3:

   • 从 Head 开始，寻找小于 36 的最大节点。
   • 移动到 33（因为 33 < 36），然后移动到 55（因为 55 > 36），停止。
   • 在 Level 3，小于 36 的最大节点是 33。

2. 下降至 Level 2:

   • 从 Level 3 中找到的最后一个节点（33）开始。
   • 在 Level 2 中，33 已经是小于 36 的最大节点，因此无需移动。
   • 在 Level 2，小于 36 的最大节点仍然是 33。

3. 下降至 Level 1:

   • 从 Level 2 中找到的节点（33）开始。
   • 33 后面是 37，但因为 37 > 36，停止移动。
   • 在 Level 1，小于 36 的最大节点是 33。

4. 下降至 Level 0:

   • 从 Level 1 中找到的节点（33）开始。
   • 33 后面是 35（35 < 36），移动到 35。
   • 35 后面是 37，但因为 37 > 36，停止移动。
   • 在 Level 0，小于 36 的最大节点是 35。

find 结果:

• Level 3 中小于 36 的最大节点是 33。
• Level 2 中小于 36 的最大节点是 33。
• Level 1 中小于 36 的最大节点是 33。
• Level 0 中小于 36 的最大节点是 35。

通过这个过程，find 函数有效地确定了在每个层级中小于目标值 36 的最大节点。这个信息可以用于后续的插入、搜索或删除操作，因为它提供了每个层级中开始这些操作的正确节点。

    // 辅助函数：找到小于目标值 target 的每一层的最大节点
    void find(int target, vector<Node*>& p) {
        Node* node = head;
        for (int i = level - 1; i >= 0; i--) {
            while (node->next[i] && node->next[i]->val < target) {
                node = node->next[i]; // 在第 i 层向前移动，直到找到小于 target 的最大节点
            }
            p[i] = node; // 存储每一层找到的节点
        }
    }

search

为了说明如何在给定的跳表中查找值为 18 的节点。

初始跳表状态:

Level 3:  Head -> 11 -------------------------------------------> 33 -------------------------------------------> 55 -> NULL
Level 2:  Head -> 11 -------------------> 22 -------------------> 33 -------------------> 44 -------------------> 55 -------------------> 66 -> NULL
Level 1:  Head -> 11 -------> 15 -------> 22 -------> 27 -------> 33 -------> 37 -------> 44 -------> 48 -------> 55 -------> 59 -------> 66 -------> 72 -> NULL
Level 0:  Head -> 11 -> 13 -> 15 -> 18 -> 22 -> 24 -> 27 -> 30 -> 33 -> 35 -> 37 -> 40 -> 44 -> 46 -> 48 -> 51 -> 55 -> 57 -> 59 -> 61 -> 66 -> 69 -> 72 -> 75 -> NULL

执行 search(18) 的步骤:

1. 开始于 Level 3:

   • 从 Head 开始，寻找小于 18 的最大节点。
   • 移动到 11（因为 11 < 18），然后到 33（因为 33 > 18），停止。
   • 在 Level 3，小于 18 的最大节点是 11。

2. 下降至 Level 2:

   • 从 Level 3 中找到的最后一个节点（11）开始。
   • 在 Level 2 中，11 后面是 22，但因为 22 > 18，停止。
   • 在 Level 2，小于 18 的最大节点是

11。

3. 下降至 Level 1:

   • 从 Level 2 中找到的节点（11）开始。
   • 11 后面是 15（15 < 18），移动到 15。
   • 15 后面是 22，但因为 22 > 18，停止。
   • 在 Level 1，小于 18 的最大节点是 15。

4. 下降至 Level 0:

   • 从 Level 1 中找到的节点（15）开始。
   • 15 后面是 18，我们找到了目标节点。
   • 在 Level 0，找到了值为 18 的节点。

search 结果:

• 在 Level 0 中找到了值为 18 的节点，所以 search(18) 返回 true。

通过这个过程，search 函数在跳表的不同层级中高效地定位了值为 18 的节点。它首先在高层级中快速移动，快速跳过那些不满足条件的节点，然后逐层下降，直到在最底层找到了目标节点。通过这种方式，跳表提供了比普通链表更快的搜索性能。

    // 查找函数：判断跳表中是否存在值为 target 的节点
    bool search(int target) {
        vector<Node*> pre(level);
        find(target, pre); // 找到每一层小于 target 的最大节点
        auto p = pre[0]->next[0]; // 在最底层判断是否存在 target
        return p && p->val == target; // 如果存在且值相等，返回 true
    }

add

接下来结合具体的例子讲解如何在跳表中插入值为 36 的节点，我们将遵循 add 方法的步骤，并展示每个步骤如何在跳表的各层中影响链接。下面是跳表的当前状态，以及插入值为 36 的节点后的状态。

当前跳表状态（插入值为 36 的节点前）:

Level 3:  Head -> 11 -------------------------------------------> 33 -------------------------------------------> 55 -> NULL
Level 2:  Head -> 11 -------------------> 22 -------------------> 33 -------------------> 44 -------------------> 55 -------------------> 66 -> NULL
Level 1:  Head -> 11 -------> 15 -------> 22 -------> 27 -------> 33 -------> 37 -------> 44 -------> 48 -------> 55 -------> 59 -------> 66 -------> 72 -> NULL
Level 0:  Head -> 11 -> 13 -> 15 -> 18 -> 22 -> 24 -> 27 -> 30 -> 33 -> 35 -> 37 -> 40 -> 44 -> 46 -> 48 -> 51 -> 55 -> 57 -> 59 -> 61 -> 66 -> 69 -> 72 -> 75 -> NULL

步骤 1: 查找前驱节点

• find 函数被调用以找到跳表中每个层级上小于 36 的最大节点。
• 例如，在 Level 1 中，值为 33 的节点是 36 的前驱节点。

步骤 2: 插入新节点

• 创建一个新节点 p，值为 36。
• 在每个层级中，将新节点插入到前驱节点之后。
• 随机决定新节点出现在哪些层级中。假设随机选择它只出现在 Level 0 和 Level 1。

插入后的跳表状态:

Level 3:  Head -> 11 -------------------------------------------> 33 ---------------------------------------------------> 55 -> NULL
Level 2:  Head -> 11 -------------------> 22 -------------------> 33 ---------------------------> 44 -------------------> 55 --------------------> 66 -> NULL
Level 1:  Head -> 11 -------> 15 -------> 22 -------> 27 -------> 33 -------> [36] -> 37 -------> 44 -------> 48 -------> 55 -------> 59 --------> 66 -------> 72 -> NULL
Level 0:  Head -> 11 -> 13 -> 15 -> 18 -> 22 -> 24 -> 27 -> 30 -> 33 -> 35 -> [36] -> 37 -> 40 -> 44 -> 46 -> 48 -> 51 -> 55 -> 57 -> 59 -> 61 --> 66 -> 69 -> 72 -> 75 -> NULL

在这个图形化的表示中：

• [36] 表示新插入的节点，值为 36。
• 在 Level 1 中，新节点 [36] 被插入在值为 33 的节点和值为 37 的节点之间。即，33 -> [36] -> 37。
• 在 Level 0 中，同样的插入操作发生，将 [36] 插入在值为 35 和值为 37 的节点之间。
• 在更高层级（Level 2 和 Level 3），由于 [36] 没有被包含（基于随机选择），这些层级的链接保持不变。

通过这种方式，值为 36 的节点被有效地插入到跳表中，并且跳表的结构被适当地更新以保持其快速搜索的特性。

    // 插入函数：向跳表中插入一个值为 num 的新节点
    void add(int num) {
        vector<Node*> pre(level);
        find(num, pre); // 找到每一层小于 num 的最大节点

        auto p = new Node(num); // 创建新节点
        for (int i = 0; i < level; i++ ) {
            p->next[i] = pre[i]->next[i]; // 新节点的 next 指向前驱节点的 next
            pre[i]->next[i] = p; // 前驱节点的 next 指向新节点
            if (rand() % 2) break; // 有 50% 的概率停止向上层插入
        }
    }

erase

当我们以文本图形化的方式来讲解如何从跳表中删除一个值为 33 的节点时，我们会展示在各个层级中节点是如何被更新和移除的。以下是您提供的跳表示例，并标记了如何删除值为 33 的节点。

假设的跳表结构（删除值为 33 的节点前）:

Level 3:  Head -> 11 -------------------------------------------> 33 ----------------------------------------------> 55 -> NULL
Level 2:  Head -> 11 -------------------> 22 -------------------> 33 -------------------> 44 ----------------------> 55 ----------------> 66 -> NULL
Level 1:  Head -> 11 -------> 15 -------> 22 -------> 27 -------> 33 -------> 37 -------> 44 -------> 48 (pre[1]) -> 55 ---> 59 --------> 66 -------> 72 -> NULL
Level 0:  Head -> 11 -> 13 -> 15 -> 18 -> 22 -> 24 -> 27 -> 30 -> 33 -> 35 -> 37 -> 40 -> 44 -> 46 -> 48 -> 51 -> 55 -> 57 -> 59 -> 61 -> 66 -> 69 -> 72 -> 75 -> NULL

删除步骤:

1. 查找前驱节点:

   • 使用 find 函数在每个层级找到值为 33 的节点的前驱节点。
   • 在 Level 1 中，前驱节点是值为 27 的节点。
   • 在 Level 2 中，前驱节点是值为 22 的节点。
   • 在 Level 3 中，前驱节点是值为 11 的节点。

2. 更新指针绕过值为 33 的节点:

   • 在每个层级，将前驱节点的 next 指针指向值为 33 的节点的下一个节点。
   • 例如，在 Level 1，将值为 27 的节点的 next 指向值为 37 的节点。

跳表结构（删除值为 33 的节点后）:

Level 3:  Head -> 11 -------------------------------------------------------------------------------------> 55 -> NULL
Level 2:  Head -> 11 -------------------> 22 -------------------------------------> 44 -------------------> 55 -------------------> 66 -> NULL
Level 1:  Head -> 11 -------> 15 -------> 22 -------> 27 -------------> 37 -------> 44 -------> 48 -------> 55 -------> 59 -------> 66 -------> 72 -> NULL
Level 0:  Head -> 11 -> 13 -> 15 -> 18 -> 22 -> 24 -> 27 -> 30 -> 35 -> 37 -> 40 -> 44 -> 46 -> 48 -> 51 -> 55 -> 57 -> 59 -> 61 -> 66 -> 69 -> 72 -> 75 -> NULL

在上面的示例中，你可以看到：

• 原本指向值为 33 的节点的指针现在直接指向了它在各个层级中的下一个节点。例如，原本在 Level 1 中，值为 27 的节点指向值为 33 的节点，现在直接指向值为 37 的节点。
• 这种指针的更新在所有包含值为 33 的节点的层级中发生。因此，在 Level 0 中，值为 30 的节点的 next 现在指向值为 35 的节点，绕过了值为 33 的节点。
• 通过这种方式，值为 33 的节点从跳表的所有层级中被移除，而不影响其他节点之间的链接关系。

这就完成了删除操作。在物理层面上，值为 33 的节点将被释放，以回收内存空间。在逻辑层面上，该节点就像不存在一样，因为没有任何指针再指向它，它也不再指向其他节点。

    // 删除函数：从跳表中删除值为 num 的节点
    bool erase(int num) {
        vector<Node*> pre(level);
        find(num, pre); // 找到每一层小于 num 的最大节点

        auto p = pre[0]->next[0]; // 检查最底层是否存在要删除的节点
        if (!p || p->val != num) return false; // 如果不存在，返回 false

        // 存在则从每一层中删除
        for (int i = 0; i < level && pre[i]->next[i] == p; i++) {
            pre[i]->next[i] = p->next[i]; // 将前驱节点的 next 指向要删除节点的下一个节点
        }

        delete p; // 释放被删除节点的内存
        return true;
    }

code

下面是完整代码：

class Skiplist {
public:
    static const int level = 8; // 定义跳表的最大层数为 8，这是一个经验值，太大会造成空间浪费

    // 跳表节点的结构定义
    struct Node {
        int val; // 节点存储的值
        vector<Node*> next; // 存储到下一个节点的指针数组，next[i] 表示当前节点在第 i 层的下一个节点

        Node(int _val) : val(_val) { // 构造函数，初始化节点值和 next 数组
            next.resize(level, NULL); // 将 next 数组的大小初始化为 level，并全部指向 NULL
        }
    }*head; // 跳表的头节点，初始化时指向一个虚拟节点

    // 构造函数
    Skiplist() {
        head = new Node(-1); // 初始化头节点，使用一个不存在的节点值（这里用 -1）
    }

    // 析构函数
    ~Skiplist() {
        Node *current = head;
        while (current) {
            Node *temp = current;
            current = current->next[0]; // 遍历链表，释放每个节点的内存
            delete temp;
        }
    }

    // 辅助函数：找到小于目标值 target 的每一层的最大节点
    void find(int target, vector<Node*>& p) {
        Node* node = head;
        for (int i = level - 1; i >= 0; i--) {
            while (node->next[i] && node->next[i]->val < target) {
                node = node->next[i]; // 在第 i 层向前移动，直到找到小于 target 的最大节点
            }
            p[i] = node; // 存储每一层找到的节点
        }
    }

    // 查找函数：判断跳表中是否存在值为 target 的节点
    bool search(int target) {
        vector<Node*> pre(level);
        find(target, pre); // 找到每一层小于 target 的最大节点
        auto p = pre[0]->next[0]; // 在最底层判断是否存在 target
        return p && p->val == target; // 如果存在且值相等，返回 true
    }

    // 插入函数：向跳表中插入一个值为 num 的新节点
    void add(int num) {
        vector<Node*> pre(level);
        find(num, pre); // 找到每一层小于 num 的最大节点

        auto p = new Node(num); // 创建新节点
        for (int i = 0; i < level; i++ ) {
            p->next[i] = pre[i]->next[i]; // 新节点的 next 指向前驱节点的 next
            pre[i]->next[i] = p; // 前驱节点的 next 指向新节点
            if (rand() % 2) break; // 有 50% 的概率停止向上层插入
        }
    }

    // 删除函数：从跳表中删除值为 num 的节点
    bool erase(int num) {
        vector<Node*> pre(level);
        find(num, pre); // 找到每一层小于 num 的最大节点

        auto p = pre[0]->next[0]; // 检查最底层是否存在要删除的节点
        if (!p || p->val != num) return false; // 如果不存在，返回 false

        // 存在则从每一层中删除
        for (int i = 0; i < level && pre[i]->next[i] == p; i++) {
            pre[i]->next[i] = p->next[i]; // 将前驱节点的 next 指向要删除节点的下一个节点
        }

        delete p; // 释放被删除节点的内存
        return true;
    }
};

/**
 * Skiplist 对象的实例化和使用：
 * Skiplist* obj = new Skiplist();
 * bool param_1 = obj->search(target);
 * obj->add(num);
 * bool param_3 = obj->erase(num);
 */