**跳跃表（Skip List）**是一种 概率型数据结构，用于实现 有序集合或有序字典，功能类似于平衡二叉搜索树（如红黑树），但实现更简单。它由 多层链表组成，通过“跳跃”快速定位元素，因此叫 skip list。

很多系统都在用它，比如：

• Redis 的有序集合（Sorted Set）
• LevelDB 的内部索引结构

---

一、核心思想

普通链表查找需要 从头遍历

例如：

1 → 3 → 5 → 7 → 9 → 11

查找 9 需要：

1 → 3 → 5 → 7 → 9

时间复杂度：

O(n)

---

跳跃表通过 增加多层索引 来加速查找。

示意结构：

Level 3:        1 ----------- 9
Level 2:        1 -----5-----9
Level 1:        1--3--5--7--9--11
Level 0:  1--3--5--7--9--11

查找 9 时：

Level3: 1 → 9

只需 几步就找到。

时间复杂度变成：

O(log n)

---

二、节点结构

每个节点包含 多层指针：

struct Node {
    int val;
    Node* forward[MAX_LEVEL];
};

例子：

节点5

level3 → null
level2 → 9
level1 → 7
level0 → 7

层数越高，跳跃距离越大。

---

三、查找过程

查找 target：

从最高层开始

示例：

Level3: 1 -------- 9
Level2: 1 ----5----9
Level1: 1-3-5-7-9-11

查找 7：

步骤：

Level3: 1 → 9 (超过) ↓
Level2: 1 → 5 → 9 (超过) ↓
Level1: 5 → 7 (找到)

---

时间复杂度：

O(log n)

---

四、插入过程

插入 6：

原链表：

1 3 5 7 9

步骤：

1 随机生成层数

例如：

level = 2

2 找到每层插入位置

1 → 3 → 5 → 7

3 更新指针

插入后：

Level2: 1 ----5----6----9
Level1: 1-3-5-6-7-9
Level0: 1-3-5-6-7-9

---

五、删除

删除类似链表操作：

1. 找到每一层前驱节点
2. 修改 forward 指针

prev->next = node->next

---

六、复杂度

操作	时间复杂度
查找	O(log n)
插入	O(log n)
删除	O(log n)
空间	O(n)

---

七、为什么要随机层数

跳跃表 不需要复杂的旋转维护。

层数用概率生成：

P(level = i) = 1/2^i

生成方式：

int randomLevel() {
    int level = 1;
    while(rand() % 2)
        level++;
    return level;
}

这样保证：

n/2 个 level1
n/4 个 level2
n/8 个 level3

结构近似：

log₂ n 层

---

八、和红黑树比较

特性	Skip List	红黑树
实现难度	简单	复杂
性能	O(log n)	O(log n)
维护	概率	严格平衡
代码量	少	多

很多工程系统更喜欢 skip list。

---

九、简单 C++ 实现（核心结构）

#include <iostream>
#include <vector>
using namespace std;

const int MAX_LEVEL = 16;

struct Node {
    int val;
    vector<Node*> forward;

    Node(int v, int level) : val(v), forward(level, nullptr) {}
};

class SkipList {
    Node* head;
    int level;

public:
    SkipList() {
        head = new Node(-1, MAX_LEVEL);
        level = 1;
    }

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

    void insert(int val) {
        Node* update[MAX_LEVEL];
        Node* cur = head;

        for(int i=level-1;i>=0;i--){
            while(cur->forward[i] && cur->forward[i]->val < val)
                cur = cur->forward[i];
            update[i] = cur;
        }

        int newLevel = randomLevel();
        Node* node = new Node(val, newLevel);

        for(int i=0;i<newLevel;i++){
            node->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = node;
        }

        level = max(level, newLevel);
    }
};

---

十、为什么算法竞赛很少用

因为：

常数较大
实现复杂
STL 已有 set/map

所以竞赛更多用：

set
map
平衡树

---

如果你学 数据结构 / OI / 算法竞赛，我可以再给你讲一个非常重要的东西：

跳跃表 vs 块状链表 vs 平衡树

以及：

为什么 Redis 用 Skip List 而不用红黑树

这个其实是数据结构里非常经典的一题。