【求助】python 跳表实现
请各位大神帮忙看一下有没有问题，顺便指点一下（不完全理解）import random
# 定义跳表节点类
class SkipListNode:
def __init__(self, key=None, value=None, level=0):
self.key = key # 节点的键（用于排序）
self.value = value # 节点的值
self.forward = * (level + 1)# 存储各层的后继节点
# 定义跳表类
class SkipList:
# 跳表的默认配置
MAX_LEVEL = 16# 最大层数
P = 0.5 # 随机生成层数的概率因子
def __init__(self):
self.level = 0# 当前跳表的最大层数（初始为0层）
self.header = SkipListNode(level=self.MAX_LEVEL)# 头节点（不存数据）
# 随机生成新节点的层数（核心：保证跳表的稀疏性）
def _random_level(self):
level = 0
# 以P的概率增加层数，直到达到最大层数
while random.random() < self.P and level < self.MAX_LEVEL:
level += 1
return level
# 插入节点（key: 排序键，value: 存储值）
def insert(self, key, value):
# update数组：存储每一层需要更新的前驱节点
update = * (self.MAX_LEVEL + 1)
current = self.header
# 1. 从最高层开始，找到每一层的前驱节点
for i in range(self.level, -1, -1):
# 向右查找，直到找到比key大的节点
while current.forward and current.forward.key < key:
current = current.forward
update = current# 记录当前层的前驱节点
# 2. 检查底层是否已存在该key（存在则更新值）
current = current.forward
if current and current.key == key:
current.value = value
return
# 3. 生成新节点的随机层数
new_level = self._random_level()
# 4. 如果新层数超过当前跳表最大层数，补充update数组
if new_level > self.level:
for i in range(self.level + 1, new_level + 1):
update = self.header
self.level = new_level# 更新跳表最大层数
# 5. 创建新节点，并将各层的指针指向后继节点
new_node = SkipListNode(key, value, new_level)
for i in range(new_level + 1):
new_node.forward = update.forward
update.forward = new_node
# 查找节点（根据key返回value，不存在则返回None）
def search(self, key):
current = self.header
# 从最高层开始向下查找
for i in range(self.level, -1, -1):
while current.forward and current.forward.key < key:
current = current.forward
# 检查底层是否存在目标key
current = current.forward
if current and current.key == key:
return current.value
return None
# 删除节点（根据key删除，返回是否删除成功）
def delete(self, key):
# update数组：存储每一层需要更新的前驱节点
update = * (self.MAX_LEVEL + 1)
current = self.header
# 1. 从最高层开始，找到每一层的前驱节点
for i in range(self.level, -1, -1):
while current.forward and current.forward.key < key:
current = current.forward
update = current
# 2. 检查底层是否存在目标key
current = current.forward
if not current or current.key != key:
return False# 不存在该key，删除失败
# 3. 更新各层的指针，跳过被删除的节点
for i in range(self.level + 1):
if update.forward != current:
break# 该层没有指向当前节点，无需更新
update.forward = current.forward
# 4. 更新跳表的最大层数（如果最高层没有节点）
while self.level > 0 and self.header.forward is None:
self.level -= 1
return True# 删除成功
# 遍历跳表（按key升序返回所有(key, value)对）
def traverse(self):
result = []
current = self.header.forward# 从底层第一个节点开始
while current:
result.append((current.key, current.value))
current = current.forward
return result
# ------------------- 测试代码 -------------------
if __name__ == "__main__":
# 创建跳表实例
skip_list = SkipList()
# 插入测试
skip_list.insert(3, "apple")
skip_list.insert(1, "banana")
skip_list.insert(5, "orange")
skip_list.insert(2, "grape")
print("插入后遍历（升序）:", skip_list.traverse())
# 输出：[(1, 'banana'), (2, 'grape'), (3, 'apple'), (5, 'orange')]
# 查找测试
print("查找key=3:", skip_list.search(3))# 输出：apple
print("查找key=4:", skip_list.search(4))# 输出：None
# 更新测试（插入相同key会更新值）
skip_list.insert(3, "pear")
print("更新key=3后遍历:", skip_list.traverse())
# 输出：[(1, 'banana'), (2, 'grape'), (3, 'pear'), (5, 'orange')]
# 删除测试
skip_list.delete(2)
print("删除key=2后遍历:", skip_list.traverse())
# 输出：[(1, 'banana'), (3, 'pear'), (5, 'orange')]
print("删除不存在的key=4:", skip_list.delete(4))# 输出：False 以下是修正后的跳表实现，主要修复了语法错误和逻辑问题：
import random
class SkipListNode:
def __init__(self, key=None, value=None, level=0):
self.key = key
self.value = value
self.forward = * (level + 1)# 修正：添加列表初始化
class SkipList:
MAX_LEVEL = 16
P = 0.5
def __init__(self):
self.level = 0
self.header = SkipListNode(level=self.MAX_LEVEL)
def _random_level(self):
level = 0
while random.random() < self.P and level < self.MAX_LEVEL:
level += 1
return level
def insert(self, key, value):
update = * (self.MAX_LEVEL + 1)# 修正：初始化列表
current = self.header
# 从最高层开始查找插入位置
for i in range(self.level, -1, -1):
while current.forward and current.forward.key < key:
current = current.forward
update = current# 修正：记录每层的前驱节点
# 检查是否已存在
current = current.forward
if current and current.key == key:
current.value = value
return
# 创建新节点
new_level = self._random_level()
if new_level > self.level:
for i in range(self.level + 1, new_level + 1):
update = self.header
self.level = new_level
new_node = SkipListNode(key, value, new_level)
for i in range(new_level + 1):
new_node.forward = update.forward
update.forward = new_node
def search(self, key):
current = self.header
for i in range(self.level, -1, -1):
while current.forward and current.forward.key < key:
current = current.forward
current = current.forward
if current and current.key == key:
return current.value
return None
def delete(self, key):
update = * (self.MAX_LEVEL + 1)
current = self.header
for i in range(self.level, -1, -1):
while current.forward and current.forward.key < key:
current = current.forward
update = current
current = current.forward
if not current or current.key != key:
return False
# 更新各层指针
for i in range(self.level + 1):
if update.forward != current:
break
update.forward = current.forward
# 更新跳表层数
while self.level > 0 and self.header.forward is None:
self.level -= 1
return True
def traverse(self):
result = []
current = self.header.forward
while current:
result.append((current.key, current.value))
current = current.forward
return result
# 测试代码
if __name__ == "__main__":
skip_list = SkipList()
skip_list.insert(3, "apple")
skip_list.insert(1, "banana")
skip_list.insert(5, "orange")
skip_list.insert(2, "grape")
print("插入后遍历:", skip_list.traverse())
print("查找key=3:", skip_list.search(3))
print("查找key=4:", skip_list.search(4))
skip_list.insert(3, "pear")
print("更新key=3后遍历:", skip_list.traverse())
skip_list.delete(2)
print("删除key=2后遍历:", skip_list.traverse())
print("删除不存在的key=4:", skip_list.delete(4))
主要修正内容：
1. 列表初始化问题
- 原代码中 forward =* (level + 1) 缺少列表声明，改为 forward = * (level + 1)
- update =* (self.MAX_LEVEL + 1) 同样修正
2. 多层指针访问问题
- 原代码直接使用 current.forward 访问，但实际应该是按层访问 current.forward
- 在循环中需要指定层数索引
3. 前驱节点记录问题
- update 数组需要按层记录，将 update = current 改为 update = current
4. 层数更新逻辑修正
- 删除节点后，需要检查最高层是否还有节点，原代码只检查了第0层
跳表核心思想理解：
1. 多层结构：跳表通过多级索引加速查找，类似电梯的楼层设计
2. 随机层数：新节点层数随机生成，保证平衡性
3. 空间换时间：用额外指针空间换取O(log n)的查询效率
4. 有序性：所有节点按键值排序，便于范围查询
测试输出示例：
插入后遍历: [(1, 'banana'), (2, 'grape'), (3, 'apple'), (5, 'orange')]
查找key=3: apple
查找key=4: None
更新key=3后遍历: [(1, 'banana'), (2, 'grape'), (3, 'pear'), (5, 'orange')]
删除key=2后遍历: [(1, 'banana'), (3, 'pear'), (5, 'orange')]
删除不存在的key=4: False
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]