Python递归Treap插入函数报错：'str'/'int'对象无'key'/'value'属性

你的核心问题是Treap的BST分支逻辑错误（误用value而非key做比较），加上key匹配后未终止函数导致后续逻辑混乱，两者共同引发了AttributeError和异常逻辑错误。

具体错误点与修复步骤： #

1. BST分支逻辑完全错误
   Treap作为树堆，其BST性质是基于key的大小维护左子树key小于当前节点、右子树key大于当前节点的结构，而非value。你之前用value <= node.value决定插入方向，完全违背了Treap的设计逻辑，会导致递归过程中节点结构混乱，最终触发类型错误。

修复：将分支判断改为基于key的比较：

if key < node.key:  # 小于当前节点key，插入左子树
    node.left = self._insert(node.left, key, value, priority)
    # ... 旋转逻辑
else:  # 大于当前节点key，插入右子树（key相等的情况已提前处理）
    node.right = self._insert(node.right, key, value, priority)
    # ... 旋转逻辑

2. key匹配后未终止函数
   当key == node.key时，你更新了node.value但未立即返回节点，导致代码继续执行后续插入、旋转逻辑，这会触发不必要的递归，甚至引发节点结构错误。

修复：更新value后直接return节点，终止当前函数调用：

if key == node.key:  # 如果key已存在，更新value后直接返回
    node.value = value
    return node

3. 错误的value相等判断
   你添加的if value == node.value: raise ValueError完全不符合Map的设计逻辑——Map允许将已存在的key更新为相同的value，且该判断会在更新value后立即触发，导致不必要的异常。直接删除这部分代码。

4. 代码缩进错误
   原代码中__init__和insert方法的缩进存在问题（比如self.root = None缩进不正确），会导致类方法定义失效，必须修正缩进。

5. 统一旋转方法调用
   原代码中_rotate_right用类调用，_rotate_left用实例调用，虽然都能运行，但统一用实例调用更规范。

修正后的完整代码： #

from collections import deque, defaultdict
from dataclasses import dataclass
from random      import random

@dataclass
class Node:
    ''' Node with string key, int value, float priority, and left and right children. '''
    key: str
    value: int
    priority: float
    left: 'Node' = None
    right: 'Node' = None
    
class Map:
    def __init__(self):
        self.root = None

    def insert(self, key, value, priority=None):
        try:
            self.root = self._insert(self.root, key, value, priority)
        except ValueError:
            pass

    def _insert(self, node, key, value, priority=None):
        ''' Recursively insert key, value pair into Map. '''
        # Base case: Create new Node
        if node is None:
            return Node(key, value, priority or random())
        
        # 如果key已存在，更新value后返回
        if key == node.key:
            node.value = value
            return node
        
        # 基于key的BST插入逻辑
        if key < node.key:
            node.left = self._insert(node.left, key, value, priority)
            # 维护最大堆性质：左子节点优先级更高则右旋
            if node.left.priority > node.priority:
                node = self._rotate_right(node)
        else:
            node.right = self._insert(node.right, key, value, priority)
            # 维护最大堆性质：右子节点优先级更高则左旋
            if node.right.priority > node.priority:
                node = self._rotate_left(node)
        
        return node

    @staticmethod
    def _rotate_right(p):
        cl, gr   = p.left, p.left.right
        cl.right = p
        p.left   = gr
        return cl
        
    @staticmethod
    def _rotate_left(p):
        cr, gl  = p.right, p.right.left
        cr.left = p
        p.right = gl
        return cr

验证说明 #

修正后，插入操作会正确基于key维护Treap的BST结构，同时基于优先级维护最大堆性质，key存在时仅更新value，不会触发异常或类型错误。

内容的提问来源于stack exchange，提问作者Sam C.