跳表（Skip List）是一种用于快速查找的链表结构，支持平均 O(log n) 时间复杂度的插入、删除和查找操作。它通过多级链表来加速查找过程，具有较好的随机化性能。
跳表的基本结构

跳表包含多个“层”（Levels），每一层都是一个链表，底层（Level 0）包含所有元素，而更高的层包含部分元素，这些元素被称为“跳跃节点”。这样，当进行查找操作时，可以先从较高层次的链表进行大步跳跃，逐步缩小范围，然后切换到下一层以更精确的查找。
实现跳表的步骤

    定义跳表节点类 Node：每个节点包含值 value 和指向每一层的指针 forward。
    定义跳表类 SkipList：包含插入、删除、查找等操作。
    实现随机层级：插入节点时随机分配层级。

代码实现

以下是一个简单的跳表实现：

import random

class Node:
    def __init__(self, value, level):
        self.value = value
        # 每一层的 forward 指针列表，初始化为 None
        self.forward = [None] * (level + 1)

class SkipList:
    def __init__(self, max_level):
        self.max_level = max_level # 最大层级
        self.head = Node(-1, max_level) # 头节点初始化为 -1 的值
        self.level = 0 # 当前层级

    def random_level(self):
        """随机生成层级"""
        lvl = 0
        while random.random() < 0.5 and lvl < self.max_level:
            lvl += 1
        return lvl

    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

# 随机生成层级
lvl = self.random_level()

        # 如果新节点的层级比当前跳表的层级高，则更新跳表的层级
        if lvl > self.level:
            for i in range(self.level + 1, lvl + 1):
                update[i] = self.head
            self.level = lvl

        # 创建新节点并插入
        new_node = Node(value, lvl)
        for i in range(lvl + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node
        print(f"Inserted {value} at level {lvl}")

    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 and target.value == value:
            for i in range(self.level + 1):
                if update[i].forward[i] != target:
                    break
                update[i].forward[i] = target.forward[i]

            # 更新当前跳表的最大层级
            while self.level > 0 and not self.head.forward[self.level]:
                self.level -= 1
            print(f"Deleted {value}")

    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]
        if current and current.value == value:
            print(f"Found {value}")
            return True
        print(f"{value} not found")
        return False

    def display(self):
        """打印跳表的每一层"""
        print("\nSkip List:")
        for i in range(self.level + 1):
            current = self.head.forward[i]
            print(f"Level {i}: ", end="")
            while current:
                print(current.value, end=" ")
                current = current.forward[i]
            print("")

使用示例

skiplist = SkipList(3) # 最大层级为3
skiplist.insert(3)
skiplist.insert(6)
skiplist.insert(7)
skiplist.insert(9)
skiplist.insert(12)
skiplist.insert(19)
skiplist.insert(17)

skiplist.display()

skiplist.search(9) # 输出: Found 9
skiplist.search(15) # 输出: 15 not found

skiplist.delete(6)
skiplist.display()

说明

    随机层级生成：random_level 方法根据概率随机生成一个节点的层级。
    插入：insert 方法根据生成的层级将节点插入到跳表中合适的层中。
    删除：delete 方法找到要删除的节点并从每一层的链表中移除。
    查找：search 方法遍历跳表，查看指定值是否存在。

ITPub博客

如何用 Python 实现一个跳表？

最新文章