Post

跳表（Skip List）

Posted
By 何翌闻
15 min read
跳表（Skip List）

1. 节点（Node）结构体

关键思想：跳表由多层链表组成。每个节点在第 i 层有一个 forward[i] 指针，指向该层的下一个节点；为了支持排名（rank）/区间计数，我们在每层维护一个 span[i] —— 从当前节点走 forward[i] 到下一个节点时跨越的底层节点数量（用来累加数量）。

C++ 的典型定义：

1
2
3
4
5
6
7
8
9
10

struct Node {
    int val;                     // 节点值
    vector<Node*> forward;       // 每层的下一节点指针（长度 = node_level）
    vector<int> span;            // 每层跨越数（用于 rank 计算），同长度为 node_level

    Node(int level, int value) : val(value) {
        forward.assign(level, nullptr);
        span.assign(level, 0);
    }
};

解释：

  • level（或 node_level）是该节点的高度（层数），最低为 1。
  • forward[i]：第 i 层（0 基）指向该层的下一个节点。
  • span[i]：从当前节点沿 forward[i] 指向的节点，在底层（层 0）上跨过的节点个数（包括被指向节点本身的计数效果由实现约定，下面会演示具体如何维护）。

2. 跳表主体（SkipList）结构体

需要维护的内容：

1
2
3
4
5
6

struct SkipList {
    Node* head;      // 哨兵头节点（通常高度为 MAX_LEVEL）
    int level;       // 当前跳表的最高层数（1..MAX_LEVEL）
    int size;        // 元素总数（底层节点数）
    // 构造函数等...
};

head 的 val 可以设为任意（或负无穷），head 的 forward 长度通常设为 MAX_LEVEL，但有效层数由 level 决定。

3. 随机层数（randomLevel）

用概率 P（常用 0.5）决定节点高度，经典实现：

1
2
3
4
5

int randomLevel() {
    int lvl = 1;
    while ((rand() & 1) && lvl < MAX_LEVEL) lvl++;
    return lvl;
}

或使用 double 与 P：

1
2
3
4
5

int randomLevel() {
    int lvl = 1;
    while ((double)rand()/RAND_MAX < P && lvl < MAX_LEVEL) lvl++;
    return lvl;
}

效果：高度呈几何分布，平均节点高度常数，保证期望时间复杂度 O(log n)。

跳表的核心操作（包含 rank）

下面按操作给出伪码 + 详细解释，并重点说明 span（用于 rank）如何维护。

前置：查找路径（update 数组 & rank 数组）

在插入或删除时，我们通常要先找到每层的“前驱”节点（即在该层上，紧靠目标位置左侧的节点）。保存它们到 update[0..MAX_LEVEL-1]。

同时为了维护 span，我们需要记录每层从 head 到 update[i] 已经跨越的底层节点数量，用一个 rank[i] 保存。

伪码（查找 x 的前驱）：

1
2
3
4
5
6
7

Node* cur = head
for i = level-1 downto 0:
    rank[i] = (i == level-1 ? 0 : rank[i+1]) // 可从上层传下或单独维护
    while cur.forward[i] != null and cur.forward[i].val < x:
        rank[i] += cur.span[i]   // 累加跨越数
        cur = cur.forward[i]
    update[i] = cur

解释：

  • rank[i] 表示从 head 沿第 i 层走到 update[i]，在底层上跨越了多少节点（即底层索引位置）。
  • 注意 rank 的计算方式有几种实现细节（我在代码中会用更常见的 rank[i] = 到达 update[i] 的累计底层节点数）。

插入（insert x）——详细步骤

  1. 用上面的循环找到 update[] 和 rank[]。
  2. 如果你要做“集合”不允许重复：可以先检查 update[0]->forward[0] 是否为 x，若已存在则直接返回（不插入）。
  3. 随机生成新节点的层数 lvl。
  4. 若 lvl > level，对 i = level..lvl-1 将 update[i] = head，并设 rank[i] = 0（或相应初始化），并把 head->span[i] = size（因为 head 到新节点前的所有底层节点数）。
  5. 新建节点 newNode，高度 lvl。
  6. 对每层 i = 0..lvl-1 执行：
    • newNode->forward[i] = update[i]->forward[i];
    • update[i]->forward[i] = newNode;
    • span 的关键更新：
      • newNode->span[i] = update[i]->span[i] - (rank[0] - rank[i]);
      • update[i]->span[i] = (rank[0] - rank[i]) + 1; 解释：
    • rank[0] 是到达 update[0] 的底层累积数（通常为 rank[0] = number of nodes before update[0]）。
    • (rank[0] - rank[i]) 表示在第 i 层上，update[i] 到 update[0] 之间（底层）跨过的节点数。
    • 直观理解：newNode 在第 i 层插入后，从 update[i] 到 newNode 的跨越数要变成原来 update[i] 到 newNode 的底层距离（即前面那句），而 newNode->span[i] 表示 newNode 指向原来 update[i]->forward[i] 时所跨越的数。
  7. 对 i = lvl..level-1，update[i]->span[i]++（因为在这些更高层上你并没有插入节点，但底层节点数增加了 1，跨越数需 +1）。
  8. size++。

这段 span 更新公式是跳表维护 rank 的经典实现，稍微难直观，但通过具体示例可以看清楚。

删除（erase x）——详细步骤

  1. 找到 update[]（与插入相同的查找路径）。
  2. cur = update[0]->forward[0]。确认 cur->val == x（题目保证存在）。
  3. 对每层 i = 0..level-1：
    • 若 update[i]->forward[i] != cur：说明在该层 cur 不存在，update[i]->span[i]--（底层节点少了一个）。
    • 否则（update[i]->forward[i] == cur）：
      • update[i]->span[i] += cur->span[i] - 1;
      • update[i]->forward[i] = cur->forward[i]; 解释：
    • 如果该层直接链接到被删节点 cur，则我们把 cur 的跳跃跨度 cur->span[i] 加回给 update[i]，再减去 1（因为被删节点本身已消失）。
    • 如果该层没有 cur，只是跨过了（cur 在更低层），则 update[i]->span[i]-- 表示底层节点数量少了一个。
  4. 释放 cur（或让它被回收）。
  5. 调整 level（如果最高层已无节点，则减 level）。
  6. size--。

查找（find x）

和普通跳表一样，从最高层向下走，每层尽量往右走直到下一个节点 >= x；最后判断 forward[0] 是否为 x。

时间复杂度期望 O(log n)。

计算 rank(x)（≤ x 的数量）与 countGreater(x)

用 span 我们可以在一次查找中累计：

1
2
3
4
5
6
7

cnt = 0
cur = head
for i = level-1 downto 0:
    while cur.forward[i] and cur.forward[i].val <= x:
        cnt += cur.span[i]
        cur = cur.forward[i]
return cnt

cnt 即为集合中 <= x 的个数（也就是 rank(x)）。题目要 “> x”的个数，结果为 size - rank(x)。

注意：循环里判断 <= x（包含相等） 或 < x 的差别决定了返回的是 ≤ 或 <。要小心。

4. 小例子（手把手演示）——插入序列并维护 span

我们用一个非常小的示例演示概念（为简化展示，假设 MAX_LEVEL=3，P=0.5，head 初始 level=1；我们插入元素 2, 6, 3，假设生成的随机层分别为：2 -> lvl=1，6 -> lvl=2，3 -> lvl=1）：

初始：

  • head span[0] = 0; head.forward[0] = null; size=0

插入 2 (lvl=1)：

  • update[0] = head, rank[0]=0
  • newNode level 1: newNode->span[0] = head->span[0] - (rank[0] - rank[0]) = 0
  • head->span[0] = (rank[0] - rank[0]) + 1 = 1
  • head.forward[0] -> newNode
  • size = 1

状态（层0）: head –(span=1)–> 2

插入 6 (lvl=2)：

  • 查找：update[1]=head, update[0]=node(2)
  • rank[1]=0, rank[0]=1（到达 update[0] 为 1 个）
  • lvl=2 > level(1) -> level = 2; set update[1]=head
  • newNode lvl2:
    • i=0:
      • newNode->span[0] = update[0]->span[0] - (rank[0] - rank[0]) = node(2).span[0] - 0 = 0
      • update[0]->span[0] = (rank[0] - rank[0]) + 1 = 1 (still)
    • i=1:
      • newNode->span[1] = update[1]->span[1] - (rank[0] - rank[1]) = head.span[1] - (1 - 0) （head.span[1] 假设初始为 size=1） -> head.span[1] = 1, 所以 newNode.span[1]=0
      • update[1]->span[1] = (rank[0] - rank[1]) + 1 = 2
  • 对 i = lvl..level-1 none
  • size = 2

层 1（i=0）: head –1–> 2 –1–> 6 层 2（i=1）: head –2–> 6

（注意：上面数值是示意，真实实现细节要结合初始化 head.span[] 的值）

插入 3 (lvl=1)：

  • 查找得到 update[1]=head, update[0]=node(2) 或 node(2) depending on values
  • 计算 rank，更新 span，如上所述。

这个示例说明了 span 在不同层上的重新分配：高层的 span 聚合了跨越多个低层节点的计数。插入/删除时通过 rank 分解差值并更新 span。

5. 完整且常见的 C++ 实现要点（回顾）

  • MAX_LEVEL 选 32 足以（2^32 » 5e5）。
  • head 节点通常用 MAX_LEVEL 的 forward 和 span。
  • span 的定义必须和实现保持一致（表示从当前节点沿 forward[i] 指向的节点，在底层跨越的节点总数）。
  • 插入时使用 update[] 和 rank[] 来正确计算 newNode->span 与 update->span。
  • 删除时要处理两类层：直接连接到被删节点和不直接连接的层。
  • 对集合（no-duplicate）要在插入前检查是否已存在（update[0]->forward[0]）。
  • getRank(x) 的判断条件决定是要 <= x 还是 < x。

6. 常见错误 & 调试建议

  1. span 含义混淆：最常见的错误。确定你的 span[i] 定义（是否包含目标节点）并在所有地方保持一致。上面讲解中用了“跨越的底层节点数量”，span 包含被指向节点的计数（这样方便累加 rank）。
  2. rank 初始化/传递错误：计算 rank[i] 时一定要清楚它代表什么（到 update[i] 的底层个数）。推荐从最高层向下累加或从 0 层向上累加其中一种一致做法。
  3. 随机数使用：用 rand() 时最好在程序开始 srand(time(nullptr))，但在比赛判题系统中通常不需要或不建议每次随机不同（可以固定种子以便调试），但固定种子不会影响复杂度，只影响常数时间表现。
  4. 未处理重复插入：如果是集合（no duplicates），要先检查是否存在再插入。
  5. level 更新忘记：插入可能改变跳表 level，删除后可能需降低 level。
  6. 越界访问 forward[i] 或 span[i]：节点的 forward/span 长度等于该节点的 level。访问时要确保 i < node->forward.size()。
  7. 内存泄露/重复释放：比赛环境一般不要求手动 delete，但在长时间运行服务时要注意释放。

调试技巧：

  • 在小规模数据（例如插入 1..20）下打印每层链表与 span，观察是否满足预期。
  • 写单元测试：插入一组已知值，逐次查询 rank(x) 与 countGreater(x)，与暴力数组比对。
  • 打印 update[] 和 rank[] 在关键操作前后的值。

7. 时间与空间复杂度

  • 平均时间：插入/删除/查找/rank 都是 O(log n)（期望）。
  • 最坏时间：理论上 O(n)（极低概率，取决于随机化）。
  • 空间：O(n * expected_level) ≈ O(n)（常数因子 ≈ 2）。

8. 我给你的 C++ Node/SkipList 最小实现骨架（摘取自之前代码并少许注释）：

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

const int MAX_LEVEL = 32;

struct Node {
    int val;
    vector<Node*> forward;
    vector<int> span;
    Node(int level, int v) : val(v) {
        forward.assign(level, nullptr);
        span.assign(level, 0);
    }
};

struct SkipList {
    Node* head;
    int level;
    int size;
    SkipList() {
        head = new Node(MAX_LEVEL, -1);
        level = 1;
        size = 0;
        // 初始化 head->span[*] = 0 或 = size (按实现)
    }

    int randomLevel() {
        int lvl = 1;
        while ((rand() & 1) && lvl < MAX_LEVEL) lvl++;
        return lvl;
    }

    // 查找 update[] 与 rank[]
    void findUpdateAndRank(int x, vector<Node*>& update, vector<int>& rank) {
        Node* cur = head;
        int acc = 0;
        for (int i = level - 1; i >= 0; --i) {
            rank[i] = (i == level-1 ? 0 : rank[i+1]);
            while (cur->forward[i] && cur->forward[i]->val < x) {
                rank[i] += cur->span[i];
                cur = cur->forward[i];
            }
            update[i] = cur;
        }
    }

    // 其余 insert/erase/getRank/ find 请参考之前完整代码
};

9. 小结（要点回顾）

  • 跳表通过多层“跳跃”实现 O(log n) 平均时间。
  • 为了支持 “大于 x 的个数” 这类 rank 操作，需要在每层维护 span（跨越数）。
  • 插入/删除时通过 update[]（每层前驱）与 rank[]（到前驱的底层累积） 精确调整 span。
  • 实现细节容易出现索引/含义混淆，推荐用小型测试打印每层结构调试。
数据结构与算法
笔记
This post is licensed under CC BY 4.0 by the author.

Trending Tags

笔记 随笔 插件