平衡二叉树插入和删除之后判断是否平衡的问题

Question

在插入一个节点后，从哪个节点开始判断是否平衡，删除一个节点后，在那个节点判断是否平衡？望有人回答，一定采纳，有代码演示就更好啦哈哈哈

Answer 1

平衡二叉树插入采用递归的方式，在某个结点插入后，递归返回，在返回的过程中不断地判断是否平衡。即在插入位置的根结点开始判断是否平衡，并不断回溯。
部分代码如下：

AVLNode* AVL_Insert(AVLNode* root, int val)
{
    if (!root)//root是空树，直接创建
    {
        root = new AVLNode(val);
        root->balance = Balance(root);
        return root;
    }
    if (val == root->val)//不允许出现相同的值
    {
        cout << "error!" << endl;
        return root;
    }

    if (val < root->val)//小于
    {
        root->left = AVL_Insert(root->left, val);
        root->balance = Balance(root);
        //插入成功后，进行平衡调整
        if (root->balance > 1)
        {
            if (val < root->left->val)//LL型
            {
                root = LL_Rotate(root);
            }
            else  //LR型
            {
                root = LR_Rotate(root);
            }
        }
    }
    if (val > root->val)
    {
        root->right = AVL_Insert(root->right, val);
        root->balance = Balance(root);
        //插入成功后，进行平衡调整
        if (root->balance < -1)
        {
            if (val > root->right->val)//RR型
            {
                root = RR_Rotate(root);
            }
            else  //RL型
            {
                root = RL_Rotate(root);
            }
        }
    }
    root->balance = Balance(root);
    return root;
}

如上图，找到插入的位置后递归返回，之后开始判断是否平衡；之后递归栈不断出栈，判断是否平衡。