Python 数据结构：跳表（Skip List）

# /*
# Python 数据结构：跳表（Skip List）
# --------------------------------------------------------
# 概念：
# 跳表是一种基于多层链表结构的快速查找数据结构，
# 通过“多级索引”让查找性能达到 O(log n)，
# 是替代平衡树（如红黑树）的典型结构。
#
# 特点：
# 1) 插入 / 删除 / 查找平均 O(log n)
# 2) 结构简单，易实现
# 3) 通过随机层数维持平衡
# */

import random

# --------------------------------------------------------
# 跳表节点定义
class SkipNode:
    def __init__(self, value, level):
        self.value = value              # 节点值
        self.forward = [None] * level   # 每层的前进指针


# --------------------------------------------------------
# 跳表实现
class SkipList:
    MAX_LEVEL = 6     # 最大层数
    P = 0.5           # 概率因子，用于决定层数

    def __init__(self):
        self.level = 1
        self.head = SkipNode(None, SkipList.MAX_LEVEL)

    # 随机生成层级，决定节点“高度”
    def random_level(self):
        lvl = 1
        while random.random() < SkipList.P and lvl < SkipList.MAX_LEVEL:
            lvl += 1
        return lvl

    # ----------------------------------------------------
    # 插入
    def insert(self, value):
        update = [None] * SkipList.MAX_LEVEL
        current = self.head

        # 查找插入位置
        for i in reversed(range(self.level)):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
            update[i] = current

        # 生成节点层数
        lvl = self.random_level()
        if lvl > self.level:
            for i in range(self.level, lvl):
                update[i] = self.head
            self.level = lvl

        # 创建节点
        new_node = SkipNode(value, lvl)

        # 插入节点
        for i in range(lvl):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

    # ----------------------------------------------------
    # 查找
    def search(self, value):
        current = self.head
        for i in reversed(range(self.level)):
            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 display(self):
        print("\n跳表结构：")
        for i in reversed(range(self.level)):
            node = self.head.forward[i]
            print(f"Level {i+1}: ", end="")
            layer_vals = []
            while node:
                layer_vals.append(str(node.value))
                node = node.forward[i]
            print(" -> ".join(layer_vals))


# --------------------------------------------------------
# 示例演示
sl = SkipList()

data = [3, 6, 7, 9, 12, 19, 17, 26, 21, 25]

for x in data:
    sl.insert(x)

sl.display()

print("\n查找 19:", sl.search(19))
print("查找 15:", sl.search(15))

# --------------------------------------------------------
# 要点总结：
# 1) 跳表使用多层链表提高查找速度；
# 2) 每个节点含有多个 forward 指针；
# 3) 节点高度由概率随机决定，保证平衡性；
# 4) 查找从最顶层开始，逐层向下；
# 5) 平均性能与红黑树等平衡树相同，但更易实现；
# 6) 常用于 Redis 等系统内部结构。
# */

# 跳表结构：
# Level 4: 17 -> 25
# Level 3: 17 -> 25
# Level 2: 7 -> 17 -> 25
# Level 1: 3 -> 6 -> 7 -> 9 -> 12 -> 17 -> 19 -> 21 -> 25 -> 26
#
# 查找 19: True
# 查找 15: False