AVL树右节点失衡且含双子节点时的平衡调整方法咨询

首先明确失衡节点22的状态：

• 节点22的左子树为空（高度0），右子树以49为根（高度2，因为49的左右子节点都是叶子，高度1，所以整体右子树高度是2），平衡因子为0 - 2 = -2，属于右重失衡。
• 再看22的右孩子49：它的左右子树（33和50）都是叶子，高度相等，平衡因子为0。

根据AVL树的旋转规则，这种情况属于RR型失衡（含右孩子平衡因子为0的情况），应该采用左单旋转调整，而非RL型（即你提到的DRL）的双旋转，理由如下：
RL型失衡的前提是失衡节点右重，且右孩子本身是左重状态（右孩子的左子树高度 > 右子树高度），但当前49的左右子树等高，不符合RL型的触发条件。

左单旋转的具体步骤 #

1. 将49替换22，成为19的右子节点；
2. 将22设置为49的左子节点；
3. 将49原来的左子节点33，设置为22的右子节点。

调整后的树结构如下：

19  
 /      \  
13       49  
\       /  \ 
18     22  50
       \
        33

此时整棵树重新满足AVL树的平衡条件，所有节点的平衡因子绝对值均不超过1。

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