AVL树插入旋转后子节点丢失问题排查求助

核心问题点 #

• 旋转后未更新树的根节点：原插入方法执行旋转后直接return旋转节点，但未将其赋值给self.root或对应父节点的子引用，导致旋转后的新根未接入原树，旧根保留，子节点丢失。
• 旋转类型判断错误：判断LL/LR/RR/RL时误用temp_lst[0]而非失衡节点node，导致旋转类型判断错误，执行错误操作。
• find_balance_node方法存在语法错误与逻辑缺陷：方法内if the_node is not None:后仅有注释未闭合，会触发语法报错；同时未优先选择最靠近插入点的失衡节点（AVL树需从插入点向上找第一个失衡节点），导致平衡操作在错误节点执行。
• 插入循环逻辑冗余且错误：插入节点的while循环中，移除temp_list[0]后未更新当前遍历节点，可能导致插入逻辑出错；频繁调用update_all_height重复计算高度，效率低下。
• 平衡检查循环逻辑混乱：遍历节点与找失衡节点的逻辑混杂，多次重复遍历树，且未正确处理父节点与旋转后节点的关联。

修正后的代码 #

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1  # 初始高度设为1，空节点高度为0


class AVLTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        # 递归插入并自动平衡
        self.root = self._insert_recursive(self.root, value)

    def _insert_recursive(self, node, value):
        # 普通BST插入逻辑
        if not node:
            return Node(value)
        elif value < node.data:
            node.left = self._insert_recursive(node.left, value)
        else:
            node.right = self._insert_recursive(node.right, value)

        # 更新当前节点高度
        node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))

        # 计算平衡因子
        balance = self.get_balance(node)

        # 处理四种失衡情况
        # LL型旋转
        if balance > 1 and value < node.left.data:
            return self.single_left_rotation(node)
        # RR型旋转
        if balance < -1 and value > node.right.data:
            return self.single_right_rotation(node)
        # LR型旋转
        if balance > 1 and value > node.left.data:
            node.left = self.single_right_rotation(node.left)
            return self.single_left_rotation(node)
        # RL型旋转
        if balance < -1 and value < node.right.data:
            node.right = self.single_left_rotation(node.right)
            return self.single_right_rotation(node)

        # 节点平衡时直接返回
        return node

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

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

    def single_left_rotation(self, z):
        y = z.left
        t2 = y.right

        # 执行旋转操作
        y.right = z
        z.left = t2

        # 更新节点高度
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

        # 返回旋转后的新根节点
        return y

    def single_right_rotation(self, z):
        y = z.right
        t2 = y.left

        # 执行旋转操作
        y.left = z
        z.right = t2

        # 更新节点高度
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

        # 返回旋转后的新根节点
        return y

    def breadth_first_traversal(self):
        if not self.root:
            return
        temp_lst = [self.root]
        while temp_lst:
            node = temp_lst.pop(0)
            print(f"节点值: {node.data}, 高度: {node.height}")
            if node.left:
                temp_lst.append(node.left)
            if node.right:
                temp_lst.append(node.right)


def main():
    bst = AVLTree()
    bst.insert(100)
    bst.insert(120)
    bst.insert(20)
    bst.insert(10)
    bst.insert(15)

    bst.breadth_first_traversal()


main()

修正说明 #

1. 改用递归插入逻辑：递归方式可自然从插入点向上回溯，逐个检查节点平衡，避免原循环遍历的混乱逻辑，同时正确更新父节点的子引用。
2. 修复旋转后根节点更新：递归返回时直接将旋转后的新节点赋值给父节点的子引用，确保旋转后的树结构正确接入。
3. 正确判断旋转类型：基于当前失衡节点与插入值的关系判断旋转类型，确保执行正确的旋转操作。
4. 简化高度与平衡因子计算：移除冗余的update_all_height方法，在递归插入后即时更新节点高度，提升效率。
5. 修复广度优先遍历逻辑：原遍历逻辑中root变量更新错误，修正后用队列方式正确遍历所有节点。

内容的提问来源于stack exchange，提问作者Yex