跳表（Skip List） 介绍

跳表详解

跳表（Skip List） 是一种动态数据结构，最早由 William Pugh 于 1990 年提出。它通过在有序链表的基础上引入多级索引结构，使得在有序链表中可以快速进行查找、插入和删除操作。跳表的平均时间复杂度为 O(log n)，在最坏情况下为 O(n)。

1. 跳表结构

跳表的核心思想是通过建立多级“跳跃”索引来减少遍历节点的数量。我们可以把跳表想象成一个多层的链表结构：

• 最底层是一个普通的有序链表，保存所有元素。
• 第二层是对最底层链表的一部分节点建立的索引，索引跨度为 2。
• 第三层对第二层再建立索引，索引跨度为 4，以此类推。

这种多级索引结构使得查找、插入和删除操作都能够通过从上往下跳跃，逐步缩小查找范围。

2. 跳表的时间复杂度

• 查找：在每一层索引中，从左到右进行顺序查找，如果找到合适区间，再下降到下一层继续查找，最终找到目标元素。平均时间复杂度为 O(log n)。
• 插入：在找到插入位置后，按照一定概率，更新插入元素的多级索引。
• 删除：删除操作也是先找到目标元素，然后删除元素及其相关的索引。

3. 使用场景

跳表适用于以下场景：

• 动态有序集合：当需要快速地进行插入、删除和查找操作，并且数据需要保持有序时，跳表是非常好的选择。
• 分布式系统中的有序集合：比如 Redis 的 Sorted Set（有序集合）底层就使用了跳表，跳表能够为有序数据提供高效的插入、删除、和查找。
• 内存数据库、缓存：在内存数据库或缓存中，如果需要经常进行查找和范围查询操作，跳表的性能表现良好，且比树结构更简单。

4. 示例代码

下面是用 Python 实现的跳表结构，示例中包括跳表的插入、查找、删除功能：

import random

class Node:
    def __init__(self, value=None, level=0):
        self.value = value
        self.forward = [None] * (level + 1)  # 创建一个 forward 列表，表示该节点的“前进”指针

class SkipList:
    MAX_LEVEL = 16  # 最大索引层数
    P = 0.5  # 随机生成层数的概率

    def __init__(self):
        self.level = 0  # 当前的索引层数
        self.header = Node(None, self.MAX_LEVEL)  # 跳表的头节点

    def random_level(self):
        level = 0
        while random.random() < self.P and level < self.MAX_LEVEL:
            level += 1
        return level

    def insert(self, value):
        update = [None] * (self.MAX_LEVEL + 1)  # 记录每层的待插入位置
        current = self.header
        
        # 找到插入位置
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
            update[i] = current  # 记录该层的最后一个小于待插入值的节点

        # 插入新的节点
        level = self.random_level()  # 随机生成新节点的层数
        if level > self.level:
            for i in range(self.level + 1, level + 1):
                update[i] = self.header  # 新增层索引，指向头节点
            self.level = level

        new_node = Node(value, level)
        for i in range(level + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

    def search(self, value):
        current = self.header
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
        current = current.forward[0]
        if current and current.value == value:
            return True
        return False

    def delete(self, value):
        update = [None] * (self.MAX_LEVEL + 1)
        current = self.header

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

        current = current.forward[0]
        if current and current.value == value:
            for i in range(self.level + 1):
                if update[i].forward[i] != current:
                    break
                update[i].forward[i] = current.forward[i]

            # 如果删除的是最大层节点，减少层数
            while self.level > 0 and self.header.forward[self.level] is None:
                self.level -= 1

# 测试跳表
if __name__ == "__main__":
    skiplist = SkipList()
    
    # 插入一些数据
    for num in [3, 6, 7, 9, 12, 19, 17]:
        skiplist.insert(num)
    
    # 查找数据
    print(skiplist.search(7))  # 输出 True
    print(skiplist.search(15))  # 输出 False
    
    # 删除数据
    skiplist.delete(6)
    print(skiplist.search(6))  # 输出 False

5. 总结

• 优点：跳表是一种易于实现的数据结构，平均性能与平衡树相当，但实现相对简单，并且在分布式系统中表现出色。
• 应用场景：跳表非常适合用于需要频繁查找和插入的有序数据场景，尤其是像 Redis 中的 Sorted Set 这样的数据结构。