手写跳表（Skip List）的实现

跳表是一种基于概率的数据结构，它通过多层链表来实现快速查找、插入和删除操作，时间复杂度为O(log n)。跳表可以看作是二叉搜索树的一种替代方案，实现相对简单，且不需要复杂的平衡操作。

跳表的核心思想

1. 基础层是一个完整的有序链表
2. 上层链表是下层的"快速通道"，每个节点以一定概率(p=1/2或1/4)出现在上层
3. 通过从最高层开始搜索，可以快速跳过大量节点

跳表节点的设计

import random

class SkipListNode:
    def __init__(self, val=None, level=0):
        self.val = val
        self.forward = [None] * (level + 1)  # 每层的前进指针

跳表类的实现

1. 初始化

class SkipList:
    def __init__(self, max_level=16, p=0.5):
        self.max_level = max_level  # 最大层数
        self.p = p  # 节点晋升概率
        self.level = 0  # 当前最大层数
        self.head = SkipListNode(-float('inf'), max_level)  # 头节点
        self.size = 0

2. 随机层数生成
每个新节点插入时，需要确定它应该出现在哪些层：

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

3. 查找操作
查找过程从最高层开始，逐层下降：

def search(self, target):
    current = self.head
    
    # 从最高层开始搜索
    for i in range(self.level, -1, -1):
        # 在当前层向前移动，直到找到大于等于target的节点
        while current.forward[i] and current.forward[i].val < target:
            current = current.forward[i]
    
    # 现在current是小于target的最大节点
    current = current.forward[0]
    
    if current and current.val == target:
        return True
    return False

4. 插入操作
插入需要维护每层的前驱指针：

def add(self, num):
    # 记录每层需要更新的前驱节点
    update = [None] * (self.max_level + 1)
    current = self.head
    
    # 从最高层开始，找到每层的前驱节点
    for i in range(self.level, -1, -1):
        while current.forward[i] and current.forward[i].val < num:
            current = current.forward[i]
        update[i] = current
    
    current = current.forward[0]
    
    # 如果节点已存在，可以选择更新或忽略
    if current and current.val == num:
        return  # 或更新值
    
    # 生成新节点的层数
    new_level = self.random_level()
    
    # 如果新节点的层数大于当前最大层数，更新高层的前驱
    if new_level > self.level:
        for i in range(self.level + 1, new_level + 1):
            update[i] = self.head
        self.level = new_level
    
    # 创建新节点
    new_node = SkipListNode(num, new_level)
    
    # 更新各层的指针
    for i in range(new_level + 1):
        new_node.forward[i] = update[i].forward[i]
        update[i].forward[i] = new_node
    
    self.size += 1

5. 删除操作
删除需要更新各层的前驱指针：

def erase(self, num):
    update = [None] * (self.max_level + 1)
    current = self.head
    
    # 找到每层的前驱节点
    for i in range(self.level, -1, -1):
        while current.forward[i] and current.forward[i].val < num:
            current = current.forward[i]
        update[i] = current
    
    current = current.forward[0]
    
    # 如果节点不存在
    if not current or current.val != num:
        return False
    
    # 更新各层的指针
    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.head.forward[self.level] is None:
        self.level -= 1
    
    self.size -= 1
    return True

复杂度分析

• 空间复杂度：O(n)，平均每个节点有1/(1-p)个指针
• 时间复杂度：
  • 查找：O(log n)
  • 插入：O(log n)
  • 删除：O(log n)

实际应用场景

1. Redis的有序集合(zset)
2. LevelDB、RocksDB的MemTable
3. 需要快速范围查询的场景

优化技巧

1. 设置合适的最大层数(通常16-32)
2. 调整晋升概率p(通常0.25-0.5)
3. 可以添加尾指针加速范围查询

跳表通过简单的随机化实现了平衡树的性能，是工程实践中常用的高效数据结构。