跳表（Skip List）

跳表（Skip List）

跳表是一种概率性的数据结构，它允许在有序序列中进行快速的搜索、插入和删除操作，平均时间复杂度为$O(\log n)$。跳表通过多层链表实现，每一层都是下一层的“快速通道”，从而减少查找所需的比较次数。

基本概念

跳表由多层链表组成，其中：

• 第0层（最底层）包含所有元素，并按升序排列。
• 更高层是第0层的子集，通过随机方式选择部分节点作为“索引节点”，以加速查找。

跳表的效率来源于其分层结构，类似于二分查找的思想，但实现上更简单且动态。

结构示例

graph LR A[Head] --> B[3] A --> C[6] A --> D[9] B --> E[1] B --> F[3] C --> G[6] D --> H[9] E --> I[1] E --> J[2] F --> K[3] F --> L[5] G --> M[6] G --> N[7] H --> O[9] I --> P[1] J --> Q[2] K --> R[3] L --> S[5] M --> T[6] N --> U[7] O --> V[9]

上图展示了一个跳表的简化结构，其中高层（如Head→3→6→9）帮助快速定位目标范围，而底层（如1→2→3→5→6→7→9）存储完整数据。

核心操作

查找

从最高层开始，向右遍历直到找到大于或等于目标的节点，然后向下移动一层继续搜索，直到第0层。

插入

1. 在第0层插入节点。 2. 随机决定是否将该节点提升到更高层（通常以50%的概率）。

删除

从最高层开始查找目标节点，并在所有层中删除它。

代码实现

以下是Python实现的跳表示例：

import random

class SkipListNode:
    def __init__(self, val=None, levels=0):
        self.val = val
        self.forward = [None] * levels

class SkipList:
    def __init__(self, max_level=16, p=0.5):
        self.max_level = max_level
        self.p = p
        self.head = SkipListNode(levels=max_level)
        self.level = 1

    def random_level(self):
        level = 1
        while random.random() < self.p and level < self.max_level:
            level += 1
        return level

    def insert(self, val):
        update = [None] * self.max_level
        current = self.head

        for i in range(self.level-1, -1, -1):
            while current.forward[i] and current.forward[i].val < val:
                current = current.forward[i]
            update[i] = current

        new_level = self.random_level()
        if new_level > self.level:
            for i in range(self.level, new_level):
                update[i] = self.head
            self.level = new_level

        new_node = SkipListNode(val, new_level)
        for i in range(new_level):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

    def search(self, val):
        current = self.head
        for i in range(self.level-1, -1, -1):
            while current.forward[i] and current.forward[i].val < val:
                current = current.forward[i]
        current = current.forward[0]
        return current and current.val == val

# 示例用法
sl = SkipList()
sl.insert(3)
sl.insert(6)
sl.insert(7)
print(sl.search(6))  # 输出: True
print(sl.search(4))  # 输出: False

复杂度分析

• 空间复杂度：$O(n)$（平均每层存储约$n/2^i$个节点）。
• 时间复杂度：

 * 查找/插入/删除：平均$O(\log n)$，最坏$O(n)$（当所有节点集中在高层时）。

实际应用

1. Redis的有序集合：使用跳表实现高效的区间查询和排序。 2. LevelDB/RocksDB：作为内存中的索引结构。 3. 并发数据结构：跳表的无锁实现可用于多线程环境。

对比其他数据结构

跳表 vs 平衡树

特性	跳表	平衡树（如AVL树）
实现复杂度	简单	复杂
平均时间复杂度	$O(\log n)$	$O(\log n)$
范围查询效率	高（线性遍历底层）	中（需要中序遍历）

总结

跳表通过概率性的分层设计，在保持简单实现的同时达到了与平衡树相当的效率，尤其适合需要频繁插入/删除的场景。它是现代数据库和缓存系统中不可或缺的数据结构之一。