AVL树右右/右左复合失衡旋转方法及失衡场景判定咨询

1. 若AVL树同时处于右右失衡与右左失衡，应如何进行旋转操作？ #

这两种失衡场景不可能同时出现，因为它们的判定条件互斥：

• 右右失衡：失衡节点的右子树高度比左子树高2，且右子树的右分支高度≥左分支高度
• 右左失衡：失衡节点的右子树高度比左子树高2，且右子树的左分支高度>右分支高度
  两者的判定逻辑完全互斥，不存在同时满足的情况，因此不需要考虑这种场景下的旋转操作。

2. 删除节点后的AVL树失衡类型判定 #

首先定位失衡节点：删除T0的叶子节点后，树的失衡节点为最顶端的节点，其右子树高度比左子树高2。
再看该失衡节点的右子节点的子树高度：右子节点的左子树高度大于右子树高度，因此该失衡属于右左失衡（Right-Left case）。

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