跳表（Skip List）的实现

题目描述
跳表是一种可以在有序链表基础上实现高效查找、插入、删除的数据结构。它通过维护多级索引（即多层链表），使得查找、插入、删除的平均时间复杂度可以达到O(log n)，最坏情况下为O(n)。跳表是平衡树（如红黑树、AVL树）的一种概率性替代方案，其实现相对简单，在Redis等系统中有关键应用。本题要求你理解跳表的原理，并能够手写实现一个基本的跳表。

解题过程详解

核心思想
想象一个有序链表，查找时需要从头到尾扫描，效率是O(n)。跳表的核心思想是“建立快速通道”（索引）：

1. 底层（第0层）是所有元素按序排列的链表。
2. 上面每一层都是下一层的“快速通道”，包含下一层的部分节点作为索引。
3. 查找时，从最高层索引开始，向右查找（如果下一个节点值小于等于目标，则继续向右），如果下一个节点值大于目标或为空，则“下降”到下一层继续查找。这个过程类似于“先坐高铁，再换乘地铁，最后步行”，可以跳过大量不需要比较的节点。

关键设计

1. 节点结构：每个节点包含值（val）、一个next指针数组（vector<Node*> next）。next[i]指向该节点在第i层索引的下一个节点。
2. 层高随机化：为了避免最坏情况，每个新插入节点的层高是随机决定的。通常采用“抛硬币”法：从第1层开始，每次有p（例如0.5）的概率向上升一层，直到随机数不满足条件。这保证了上层索引节点数量大致是下层的1/p，从而形成类似“二分”的查找结构。
3. 头节点：一个特殊的、不存储实际数据的节点，其层高为当前跳表的最大层高，next[i]指向第i层索引的第一个实际节点（如果存在）。

实现步骤

步骤1：定义节点结构和跳表类框架

#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

// 跳表节点定义
struct SkipListNode {
    int val;
    vector<SkipListNode*> next; // 每层的下一个指针
    SkipListNode(int _val, int level) : val(_val), next(level, nullptr) {}
};

class SkipList {
private:
    SkipListNode* head; // 头节点，不存实际数据
    int maxLevel;       // 跳表当前最大层数
    const float P = 0.5; // 层高增长概率
    int randomLevel() {
        int level = 1;
        // 随机生成层数，每次有P的概率向上增加一层
        while ((rand() / (float)RAND_MAX) < P && level < maxLevel) {
            level++;
        }
        return level;
    }

public:
    SkipList(int _maxLevel = 16) : maxLevel(_maxLevel) {
        head = new SkipListNode(INT_MIN, maxLevel); // 头节点值设为最小
        srand(time(0)); // 初始化随机数种子
    }
    // 后续将实现：查找、插入、删除、析构等函数
};

步骤2：实现查找（search）操作
查找是跳表所有操作的基础。逻辑是：从最高层开始，向右找到本层最后一个小于目标值的节点，然后下降一层继续，直到第0层。最后检查第0层找到的节点的下一个节点是否等于目标值。

bool search(int target) {
    SkipListNode* cur = head;
    // 从最高层开始向下搜索
    for (int i = maxLevel - 1; i >= 0; i--) {
        // 在当前层向右移动，直到下一个节点值 >= 目标
        while (cur->next[i] != nullptr && cur->next[i]->val < target) {
            cur = cur->next[i];
        }
        // 此时cur是第i层最后一个值小于target的节点
    }
    // 现在cur在第0层。检查下一个节点是否等于target
    cur = cur->next[0];
    return (cur != nullptr && cur->val == target);
}

步骤3：实现插入（add）操作
插入需要找到新节点在每一层的前驱节点，然后像链表插入一样逐层连接。关键在于这个“前驱节点数组”的获取。

1. 用一个数组update记录每一层中，新节点应该插入在哪个节点之后（即前驱节点）。
2. 从最高层开始，和查找类似，找到每一层最后一个小于num的节点，记录到update[i]。
3. 随机生成新节点的层高level。
4. 创建新节点，并更新从第0层到第level-1层的链表指针。

void add(int num) {
    vector<SkipListNode*> update(maxLevel, nullptr);
    SkipListNode* cur = head;
    // 1. 找到每一层的前驱节点
    for (int i = maxLevel - 1; i >= 0; i--) {
        while (cur->next[i] != nullptr && cur->next[i]->val < num) {
            cur = cur->next[i];
        }
        update[i] = cur; // 记录第i层的前驱节点
    }

    // 2. 生成新节点的随机层高
    int level = randomLevel();
    SkipListNode* newNode = new SkipListNode(num, level);

    // 3. 逐层插入新节点
    for (int i = 0; i < level; i++) {
        // 在第i层，将新节点插入到update[i]之后
        newNode->next[i] = update[i]->next[i];
        update[i]->next[i] = newNode;
    }
    // 注意：如果level > 当前某些层的最大节点数，那些层的头节点可能直接指向新节点
    // 但我们的update已经记录了头节点，所以逻辑是统一的。
}

步骤4：实现删除（erase）操作
删除操作是插入的逆过程。同样需要update数组记录要删除的节点在每一层的前驱节点。然后逐层断开连接，最后删除节点。

1. 找到目标节点在每一层的前驱节点，记录在update中。
2. 检查第0层的前驱节点的下一个节点是否是目标节点（即val == num）。如果不是，说明目标不存在。
3. 如果是，则从最高层到第0层，将前驱节点的指针指向目标节点的下一个节点。
4. 删除目标节点。

bool erase(int num) {
    vector<SkipListNode*> update(maxLevel, nullptr);
    SkipListNode* cur = head;
    // 1. 找到每一层的前驱节点
    for (int i = maxLevel - 1; i >= 0; i--) {
        while (cur->next[i] != nullptr && cur->next[i]->val < num) {
            cur = cur->next[i];
        }
        update[i] = cur;
    }
    // 2. 确认要删除的节点是否存在
    cur = cur->next[0]; // 第0层中，值 >= num 的第一个节点
    if (cur == nullptr || cur->val != num) {
        return false; // 节点不存在
    }
    // 3. 逐层断开连接
    for (int i = 0; i < cur->next.size(); i++) {
        // 如果前驱节点的第i层后继不是cur，说明cur在第i层没有出现，无需处理
        if (update[i]->next[i] != cur) {
            break; // 因为层是从下往上建的，上面的层可能没有这个节点
        }
        update[i]->next[i] = cur->next[i];
    }
    // 4. 删除节点
    delete cur;
    return true;
}

步骤5：内存管理与析构
跳表需要遍历第0层链表，逐个删除所有节点。

~SkipList() {
    SkipListNode* node = head->next[0];
    while (node != nullptr) {
        SkipListNode* temp = node;
        node = node->next[0];
        delete temp;
    }
    delete head;
}

总结与复杂度分析

• 时间复杂度：
  • 查找、插入、删除的平均时间复杂度均为O(log n)，其中n是节点数。得益于索引的随机化，使得每层能跳过大约一半的节点（当P=0.5时）。
  • 最坏情况O(n)（例如所有节点都只有一层索引时，退化成有序链表）。
• 空间复杂度：平均O(n)，因为每个节点平均有1/(1-P)个指针（当P=0.5时，平均每个节点有2个指针）。

核心要点回顾

1. 随机层高：这是跳表能保持平衡的关键，避免了手动重新平衡的复杂性。
2. 查找路径：查找时总是从高层向低层、在每一层向右搜索，决定了update数组的记录方式。
3. 前驱数组：插入和删除都需要先获取update数组，它记录了在每一层中，目标位置的前一个节点。

理解并实现跳表，能帮助你深刻理解“空间换时间”和“概率平衡”的思想，这是解决许多设计类问题的利器。