BST平衡旋转模式判断函数正确性排查及树未完全平衡问题咨询

一、BST是否要求每个节点保持平衡？ #

普通的二叉搜索树（BST）没有强制要求每个节点平衡，它只需要满足「左子树所有节点值小于根节点、右子树所有节点值大于根节点」的核心规则。只有自平衡二叉搜索树（比如AVL树、红黑树）才会要求每个节点的左右子树高度差控制在特定范围内（AVL树要求高度差不超过1）。你遇到的「旋转后仍有节点不平衡」的问题，应该是针对AVL这类自平衡树的场景。

二、check_which_pattern_has_occured函数问题分析 #

你的函数逻辑是通过连续两步选择高度更高的子节点来判断旋转模式，但存在以下关键漏洞：

1. 旋转模式判断逻辑偏离规则
   AVL树的旋转模式是基于失衡节点的子节点高度方向来判断的：

   • 假设失衡节点为A，左子树高度比右子树高2：
     • 若A的左子节点B的左子树高度 ≥ 右子树高度，属于**左左（zigzig_left）**模式，需右旋；
     • 若B的右子树高度 > 左子树高度，属于**左右（zigzag_left_right）**模式，需先左旋B再右旋A。
       但你的代码是从传入的p_root开始连续两步选高子树，若传入的不是真正的失衡节点，或某一步子树高度相等时直接返回no_pattern，会完全错过正确的旋转判断。

2. 子树高度相等时的错误处理
   代码中只要某一步左右子树高度相等，就返回no_pattern，但AVL树规则中，当子节点的左右子树高度相等时，依然属于zig-zig模式（比如左子节点左右子树等高，按左左处理即可），不需要返回无模式。

3. 未针对失衡节点做前置判断
   该函数的输入应该是已经确定失衡的节点（即左右子树高度差超过1的节点），如果你的调用逻辑是随意传入节点（比如根节点），会导致判断的旋转模式完全不符合当前失衡情况，旋转后自然无法解决所有节点的失衡问题。

三、代码修正建议 #

针对上述问题，调整函数逻辑如下：

int Binary_Tree::check_which_pattern_has_occured(Node_BT* unbalanced_node) {
    // 先确认当前节点确实失衡（左右高度差>1）
    int left_h = get_height_of_BT_structure(unbalanced_node->mp_left);
    int right_h = get_height_of_BT_structure(unbalanced_node->mp_right);
    if (abs(left_h - right_h) <= 1) {
        return linking_pattern::no_pattern;
    }

    // 判断失衡方向
    if (left_h > right_h) {
        // 左子树更高，看左子节点的失衡方向
        Node_BT* left_child = unbalanced_node->mp_left;
        int left_child_left_h = get_height_of_BT_structure(left_child->mp_left);
        int left_child_right_h = get_height_of_BT_structure(left_child->mp_right);
        
        if (left_child_left_h >= left_child_right_h) {
            return linking_pattern::zigzig_left; // 左左模式
        } else {
            return linking_pattern::zigzag_left_right; // 左右模式
        }
    } else {
        // 右子树更高，看右子节点的失衡方向
        Node_BT* right_child = unbalanced_node->mp_right;
        int right_child_left_h = get_height_of_BT_structure(right_child->mp_left);
        int right_child_right_h = get_height_of_BT_structure(right_child->mp_right);
        
        if (right_child_right_h >= right_child_left_h) {
            return linking_pattern::zigzig_right; // 右右模式
        } else {
            return linking_pattern::zigzag_right_left; // 右左模式
        }
    }
}

四、额外排查点 #

• 确认get_height_of_BT_structure函数的正确性：该函数需要正确计算子树高度（空树高度为0，叶子节点高度为1，以此类推），若高度计算错误，会导致整个旋转模式判断和平衡检查失效。
• 确认旋转操作的正确性：旋转不仅要调整节点指针，还要更新相关节点的高度（如果树节点存储了高度值），否则后续高度计算会出错。
• 平衡检查函数is_BT_balanced需要递归检查所有节点的左右子树高度差是否符合要求，而非仅检查根节点。

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