手写跳表（Skip List）的实现

题目描述
跳表是一种基于并联链表的数据结构，通过构建多级索引实现快速查找，其查找、插入、删除操作的时间复杂度均为O(log n)。它常被用作平衡树的替代方案，因其实现简单且性能高效，在Redis等系统中广泛应用。本题要求手写跳表的核心逻辑，包括节点结构、查找、插入和删除操作。

解题步骤

1. 跳表的基本结构
跳表由多层链表组成，每层都是有序链表。底层包含所有元素，上层作为索引层。每个节点包含：

• value：存储的数据
• forward：指针数组，指向该节点在各层的下一个节点
• level：节点实际存在的层数

2. 节点定义

import random

class SkipNode:
    def __init__(self, value, level):
        self.value = value
        self.forward = [None] * (level + 1)  # 每层的下一个节点指针

3. 跳表类初始化

• 设置最大层数（如16层），避免索引过高。
• 创建头节点，其值可为最小值（如-∞），层数为最大层数。
• 初始化当前跳表的实际最高层数为0。

class SkipList:
    def __init__(self, max_level=16):
        self.max_level = max_level
        self.head = SkipNode(float('-inf'), max_level)  # 头节点
        self.level = 0  # 当前有效最高层数

4. 随机生成节点层数
插入节点时，通过随机算法决定其层数，保证上层节点数以1/2的比例递减：

• 从第1层开始，每次以50%概率增加一层，直到超过最大层数。

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

5. 查找操作
从最高层开始，向右遍历直到下一个节点值大于等于目标值，然后下降一层继续，直到底层：

• 使用update数组记录每层遍历的最后一个节点（即小于目标值的最大节点）。

    def search(self, value):
        current = self.head
        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]  # 到达底层
        return current is not None and current.value == value

6. 插入操作

• 步骤1：使用update数组记录每层应插入位置的前驱节点（类似查找过程）。
• 步骤2：随机生成新节点层数。若新层数超过当前最高层，更新最高层数。
• 步骤3：从底层到新节点层数，将新节点插入到update[i]之后。

    def insert(self, value):
        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].value < value:
                current = current.forward[i]
            update[i] = current  # 记录每层的前驱节点

        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 = SkipNode(value, new_level)
        # 逐层插入新节点
        for i in range(new_level + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

7. 删除操作

• 步骤1：类似查找，用update记录每层待删除节点的前驱。
• 步骤2：若底层找到该节点，则从底层到其层数，逐层解除链接。
• 步骤3：若删除后最高层变为空，降低跳表层数。

    def delete(self, value):
        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].value < value:
                current = current.forward[i]
            update[i] = current

        target = current.forward[0]
        if target is None or target.value != value:
            return False  # 未找到节点

        # 从底层到目标节点层数，逐层删除
        for i in range(target.level + 1):
            if update[i].forward[i] != target:
                break  # 上层可能无该节点
            update[i].forward[i] = target.forward[i]

        # 更新跳表层数（若最高层变为空）
        while self.level > 0 and self.head.forward[self.level] is None:
            self.level -= 1
        return True

8. 复杂度分析

• 时间复杂度：查找、插入、删除均为O(log n)，基于索引的二分思想。
• 空间复杂度：O(n)，索引节点总数约为n/2 + n/4 + ... ≈ n。

关键点总结

• 跳表通过随机层数平衡索引密度，避免复杂旋转操作。
• 插入时需更新所有层的前驱节点指针，删除后需检查层数收缩。
• 实际应用中可通过调整随机概率（如1/4）优化性能。