关于AVL Tree(平衡二叉树)的一点疑问

Question

关于AVL Tree(平衡二叉树)的一点疑问，LR类型，要么添加到左子树或右子树导致平衡因子+1，我的理解是不会有添加之后平衡因子不改变的情况。也就是下面代码里switch里的EH情况。我是哪里理解有问题吗？

LeftBalance函数：

void LeftBalance(BSTree* T)
{
    BSTree lc,rd;
    lc = (*T)->lchild;
    switch (lc->bf)
    {
        case LH:
            (*T)->bf = lc->bf = EH;
            R_Rotate(T);
            break;
        case RH:
            rd = lc->rchild;
            switch(rd->bf)
        {
            case LH:
                (*T)->bf = RH;
                lc->bf = EH;
                break;
            case EH:
                (*T)->bf = lc->bf = EH;
                break;
            case RH:
                (*T)->bf = EH;
                lc->bf = LH;
                break;
        }
            rd->bf = EH;
            L_Rotate(&(*T)->lchild);
            R_Rotate(T);
            break;
    }
}

Answer 1

应该是可以的吧。

首先，你提到的 EH 情况是在LeftBalance函数内部处理的一种情况。从代码来看，当lc的平衡因子为 EH 时，(*T) 和lc的平衡因子都被设置为 EH。这种情况下，添加节点之后的平衡因子就不会改变。

解释一下代码

1. 当lc的平衡因子为LH时，即左子树比右子树高。这时，将 (*T) 和 lc 的平衡因子都设置为 EH。然后进行一次右旋转操作 R_Rotate(T)。

2. 当 lc 的平衡因子为RH时，即左子树比右子树低。这时，先获取lc的右子树 rd。然后根据 rd 的平衡因子进行分情况处理：

   • 当 rd 的平衡因子为 LH 时，即左子树比右子树高。将 (*T) 的平衡因子设置为 RH，lc 的平衡因子设置为 EH。

   • 当 rd 的平衡因子为EH时，即左子树和右子树高度相等。将 (*T) 和 lc 的平衡因子都设置为 EH。

   • 当rd的平衡因子为RH时，即左子树比右子树低。将 (*T) 的平衡因子设置为 EH，lc 的平衡因子设置为 LH。

   最后，将 rd 的平衡因子设置为 EH，进行一次左旋转操作 L_Rotate(&(*T)->lchild)，然后再进行一次右旋转操作 R_Rotate(T)。

这样，通过双旋转的操作可以保持平衡因子不变，并且恢复 AVL 树的平衡。

---

---

---

应该是不会存在 EH 的情况。
如果 lc 的平衡因子为 RH，说明节点添加在了 lc 的右子树。然后再根据 rd 的平衡因子进行不同的操作。
两个情况分析看看

• 如果 rd->bf 为 LH，说明节点添加在了 rd 的左子树，此时会进行两次旋转：先进行左旋操作，再进行右旋操作。在这个过程中，平衡因子 rd->bf 会被改变，所以不会出现 EH 的情况。
• 如果 rd->bf 为 RH，说明节点添加在了 rd 的右子树，此时也会进行两次旋转：先进行左旋操作，再进行右旋操作。同样，在这个过程中，平衡因子 rd->bf 会被改变，不会存在 EH 的情况。