Python中AVL树部分节点无法删除触发AttributeError问题求助

问题根源 #

1. get_min函数逻辑错误：原函数会循环到current变为None才返回，导致获取到的最小节点是None，后续访问temp.data时触发AttributeError。
2. 删除后未检查节点是否为空：递归删除节点后，root_node可能变为None，直接访问root_node.height会引发错误。

修复后的完整代码 #

from collections import deque

class AVL_Tree:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1

    def levelOrder_Traversal(self, root_node):
        if not root_node:
            return
        q = deque()
        q.append(root_node)
        while len(q) > 0:
            node = q.popleft()
            print(node.data)

            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)

    def get_height(self, root_node):
        if not root_node:
            return 0
        return root_node.height

    def get_balance(self, root_node):
        if not root_node:
            return 0
        return self.get_height(root_node.left) - self.get_height(root_node.right)

    def rotate_right(self, node):
        new_root = node.left
        node.left = new_root.right
        new_root.right = node

        node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))
        new_root.height = 1 + max(self.get_height(new_root.left), self.get_height(new_root.right))

        return new_root

    def rotate_left(self, node):
        new_root = node.right
        node.right = new_root.left
        new_root.left = node

        node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))
        new_root.height = 1 + max(self.get_height(new_root.left), self.get_height(new_root.right))

        return new_root

    def insert_data(self, root_node, new_data):
        if not root_node:
            return AVL_Tree(new_data)
        elif new_data < root_node.data:
            root_node.left = self.insert_data(root_node.left, new_data)
        else:
            root_node.right = self.insert_data(root_node.right, new_data)

        root_node.height = 1 + max(self.get_height(root_node.left), self.get_height(root_node.right))
        balance = self.get_balance(root_node)

        # left - left condition
        if balance > 1 and new_data < root_node.left.data:
            return self.rotate_right(root_node)
        
        # left - right condition
        if balance > 1 and new_data > root_node.left.data:
            root_node.left = self.rotate_left(root_node.left)
            return self.rotate_right(root_node)
        
        # right - right condition
        if balance < -1 and new_data > root_node.right.data:
            return self.rotate_left(root_node)
        
        # right - left condition
        if balance < -1 and new_data < root_node.right.data:
            root_node.right = self.rotate_right(root_node.right)
            return self.rotate_left(root_node)
        
        return root_node

    def get_min(self, root_node):
        current = root_node
        # 循环至左子树为空，此时current即为最小节点
        while current.left:
            current = current.left
        return current
    
    def delete_data(self, root_node, data):
        if not root_node:
            return root_node

        if data < root_node.data:
            root_node.left = self.delete_data(root_node.left, data)
        elif data > root_node.data:
            root_node.right = self.delete_data(root_node.right, data)
        else:
            if not root_node.left:
                temp = root_node.right
                root_node = None
                return temp
            elif not root_node.right:
                temp = root_node.left
                root_node = None
                return temp

            temp = self.get_min(root_node.right)
            root_node.data = temp.data
            root_node.right = self.delete_data(root_node.right, temp.data)

        # 新增判断：若节点已为空，直接返回，避免后续访问属性报错
        if not root_node:
            return root_node

        root_node.height = 1 + max(self.get_height(root_node.left), self.get_height(root_node.right))
        balance = self.get_balance(root_node)

        # Left - Left condition
        if balance > 1 and self.get_balance(root_node.left) >= 0:
            return self.rotate_right(root_node)

        # Left - Right condition
        if balance > 1 and self.get_balance(root_node.left) < 0:
            root_node.left = self.rotate_left(root_node.left)
            return self.rotate_right(root_node)

        # Right - Right condition
        if balance < -1 and self.get_balance(root_node.right) <= 0:
            return self.rotate_left(root_node)

        # Right - Left condition
        if balance < -1 and self.get_balance(root_node.right) > 0:
            root_node.right = self.rotate_right(root_node.right)
            return self.rotate_left(root_node)

        return root_node


avl = AVL_Tree(30)

avl = avl.insert_data(avl, 25)
avl = avl.insert_data(avl, 35)
avl = avl.insert_data(avl, 20)
avl = avl.insert_data(avl, 15)
avl = avl.insert_data(avl, 5)
avl = avl.insert_data(avl, 10)
avl = avl.insert_data(avl, 50)
avl = avl.insert_data(avl, 60)
avl = avl.insert_data(avl, 70)
avl = avl.insert_data(avl, 65)

print("AVL Tree before deletion:")
avl.levelOrder_Traversal(avl)

print("\nAVL Tree after deleting data:")
avl = avl.delete_data(avl, 30)
avl.levelOrder_Traversal(avl)

关键修复点说明 #

1. 修正get_min函数：将循环条件从while current改为while current.left，确保返回的是实际存在的最小节点，而非None。
2. 新增节点空值检查：在计算节点高度和平衡因子前，先判断root_node是否为空，避免空对象访问属性的错误。

经过以上修复，删除[20,10,50,30,65]这些节点时，AVL树的删除逻辑可正常执行，不会触发AttributeError。

内容的提问来源于stack exchange，提问作者Derek-_-