当前位置：首页 > Python > 正文

跳表查找算法详解（Python语言实现高效有序数据查找）

主机测评网
Python
2025-12-08
252

在计算机科学中，跳表查找算法（Skip List）是一种高效的数据结构，用于在有序序列中快速查找、插入和删除元素。它由 William Pugh 在 1989 年提出，具有与平衡树相近的性能，但实现更简单。本文将用通俗易懂的方式，手把手教你用 Python 实现跳表，并深入理解其工作原理。

什么是跳表？

想象一下你在一本字典里查找单词。如果一页一页翻，效率很低。但如果字典有“索引页”——比如每10页有一个大标题，你就可以先看索引快速定位到大致区域，再细查。跳表就是这个思路！

跳表本质上是一个多层链表。最底层包含所有元素，上层是“快速通道”，只包含部分元素。层数越高，元素越少，跳跃距离越大。

跳表查找算法详解（Python语言实现高效有序数据查找）跳表查找算法 Python跳表实现高效查找数据结构跳表原理详解第1张

跳表的核心思想

分层结构：每一层都是一个有序链表。
随机化建层：新插入的节点通过抛硬币（随机）决定它出现在多少层。
从高层开始查找：查找时从最高层向右搜索，若下一个节点值过大，则下降一层继续。

Python实现跳表

下面我们用 Python 编写一个完整的跳表类。我们将实现 insert、search 和 delete 方法。

import randomclass Node:    def __init__(self, value, level):        self.value = value        # 每个节点有多个 next 指针，对应不同层        self.forward = [None] * (level + 1)class SkipList:    def __init__(self, max_level=16, p=0.5):        self.max_level = max_level  # 最大层数        self.p = p                  # 决定新节点层数的概率        self.level = 0              # 当前跳表实际层数        # 创建头节点（哨兵节点），值为 -inf        self.header = Node(float('-inf'), max_level)    def _random_level(self):        """随机生成新节点的层数"""        level = 0        while random.random() < self.p and level < self.max_level:            level += 1        return level    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]        return current is not None and current.value == value    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        current = current.forward[0]        # 如果值已存在，不重复插入        if current is None or current.value != value:            new_level = self._random_level()            # 如果新层数超过当前最大层数，更新头节点的高层指针            if new_level > self.level:                for i in range(self.level + 1, new_level + 1):                    update[i] = self.header                self.level = new_level            # 创建新节点            new_node = Node(value, new_level)            # 更新各层的指针            for i in range(new_level + 1):                new_node.forward[i] = update[i].forward[i]                update[i].forward[i] = new_node    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            return True        return False# 使用示例if __name__ == "__main__":    skiplist = SkipList()    skiplist.insert(3)    skiplist.insert(6)    skiplist.insert(7)    skiplist.insert(9)    skiplist.insert(12)        print(skiplist.search(6))   # 输出: True    print(skiplist.search(5))   # 输出: False        skiplist.delete(6)    print(skiplist.search(6))   # 输出: False