二叉搜索树平衡代码报错：AddressSanitizer栈溢出问题求助

问题描述 #

尝试通过AVL树的自平衡逻辑（从下到上检查节点平衡因子，失衡时执行对应旋转）平衡二叉搜索树，但代码无法正常运行：

• VS Code调试时触发Segmentation Fault（段错误）
• LeetCode中触发AddressSanitizer:DEADLYSIGNAL栈溢出错误

报错信息 #

30ERROR: AddressSanitizer: stack-overflow on address 0x7ffca44eafe8 (pc 0x00000034586e bp 0x7ffca44eb010 sp 0x7ffca44eaff0 T0)
30ABORTING

原代码 #

// counting nodes as height of tree
int height(TreeNode* root) 
{
    if(root == NULL)
    {
        return 0;
    }
    return max(height(root->left),height(root->right)) + 1;
}

TreeNode* LLRotation(TreeNode* p)
{
    TreeNode* q = p->left;
    q->right = p;
    
    return q;
}

TreeNode* LRRotation(TreeNode* p)
{
    TreeNode* q = p->left;
    TreeNode* r = q->right;
    
    r->right = p;
    r->left = q;
    return r;
}

TreeNode* RRRotation(TreeNode* p)
{
    TreeNode* q = p->right;
    q->left = p;
    return q;
}

TreeNode* RLRotation(TreeNode* p)
{
    TreeNode* q = p->right;
    TreeNode* r = q->left;
    
    r->left = p;
    r->right = q;
    return r;
}

TreeNode* balanceBST(TreeNode* root) {
    
    if(root == NULL)
    {
        return NULL;
    }
    
    root->left = balanceBST(root->left);
    root->right = balanceBST(root->right);
    if(root->left != NULL || root->right != NULL)
    {
        if(abs(height(root->left) - height(root->right)) > 1)
        {
            if(height(root->left) - height(root->right) == 2)
            {
                if(height(root->left->left) - height(root->left->right) == 1)
                {
                    return LLRotation(root);
                }
                else {
                    return LRRotation(root);
                }
            }
            
            if(height(root->left) - height(root->right) == -2)
            {
                if(height(root->right->left) - height(root->right->right) == -1)
                {
                    return RRRotation(root);
                }
                else {
                    return RLRotation(root);
                }
            }
        }
    }
    return root;
}

错误原因分析 #

1. 旋转函数未处理原节点子指针，导致循环引用 #

以LLRotation为例：

• 原代码中q->right = p后，p->left依然指向q，形成循环链表
• 后续调用height函数递归计算高度时，会无限遍历p->left -> q -> right -> p，最终触发栈溢出

2. LR/RL旋转逻辑错误，未保存并挂载原有子节点 #

比如LRRotation中，直接将r->left = q、r->right = p，但未处理q的右子节点和p的左子节点，既会丢失子树，也可能引发额外循环引用。

3. 冗余判断逻辑 #

if(root->left != NULL || root->right != NULL)完全多余，当左右子树都为空时，平衡因子差为0，不会进入失衡处理分支。

修复后的代码 #

// 计算树的高度
int height(TreeNode* root) 
{
    if(root == NULL)
    {
        return 0;
    }
    return max(height(root->left), height(root->right)) + 1;
}

// LL旋转：左左失衡
TreeNode* LLRotation(TreeNode* p)
{
    TreeNode* q = p->left;
    TreeNode* qRight = q->right; // 保存q原来的右子树

    // 执行旋转
    q->right = p;
    p->left = qRight; // 挂载q的右子树到p的左，避免循环

    return q;
}

// LR旋转：左右失衡
TreeNode* LRRotation(TreeNode* p)
{
    TreeNode* q = p->left;
    TreeNode* r = q->right;
    TreeNode* rLeft = r->left;
    TreeNode* rRight = r->right; // 保存r的左右子树

    // 执行旋转
    r->left = q;
    r->right = p;
    q->right = rLeft; // 挂载r原左子树到q的右
    p->left = rRight; // 挂载r原右子树到p的左

    return r;
}

// RR旋转：右右失衡
TreeNode* RRRotation(TreeNode* p)
{
    TreeNode* q = p->right;
    TreeNode* qLeft = q->left; // 保存q原来的左子树

    // 执行旋转
    q->left = p;
    p->right = qLeft; // 挂载q的左子树到p的右，避免循环

    return q;
}

// RL旋转：右左失衡
TreeNode* RLRotation(TreeNode* p)
{
    TreeNode* q = p->right;
    TreeNode* r = q->left;
    TreeNode* rLeft = r->left;
    TreeNode* rRight = r->right; // 保存r的左右子树

    // 执行旋转
    r->left = p;
    r->right = q;
    p->right = rLeft; // 挂载r原左子树到p的右
    q->left = rRight; // 挂载r原右子树到q的左

    return r;
}

TreeNode* balanceBST(TreeNode* root) {
    if(root == NULL)
    {
        return NULL;
    }

    // 先递归平衡左右子树
    root->left = balanceBST(root->left);
    root->right = balanceBST(root->right);

    // 检查当前节点是否失衡
    int balance = height(root->left) - height(root->right);
    if(abs(balance) > 1)
    {
        // 左子树过重
        if(balance == 2)
        {
            // 左左型
            if(height(root->left->left) >= height(root->left->right))
            {
                return LLRotation(root);
            }
            // 左右型
            else
            {
                return LRRotation(root);
            }
        }
        // 右子树过重
        else if(balance == -2)
        {
            // 右右型
            if(height(root->right->right) >= height(root->right->left))
            {
                return RRRotation(root);
            }
            // 右左型
            else
            {
                return RLRotation(root);
            }
        }
    }

    return root;
}

额外优化点 #

• 将平衡因子计算提前存入变量，避免重复调用height函数，提升效率
• 调整失衡类型判断条件为>=/<=，覆盖左右子树高度相等的边界情况（AVL树允许此类情况，不影响平衡）

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