AVL树插入后正确旋转方式及插入2时双旋转原因咨询

AVL树的核心要求是每个节点的**平衡因子（左子树高度 - 右子树高度）**绝对值不超过1。插入节点后若出现失衡，需根据失衡节点及其直接子节点的平衡因子符号，选择对应旋转方式：

四种核心旋转场景 #

• LL型（左左失衡）：失衡节点平衡因子为+2，其左子节点平衡因子为+1 → 对失衡节点执行右旋（单旋转）
• RR型（右右失衡）：失衡节点平衡因子为-2，其右子节点平衡因子为-1 → 对失衡节点执行左旋（单旋转）
• LR型（左右失衡）：失衡节点平衡因子为+2，其左子节点平衡因子为-1 → 先对左子节点执行左旋，再对失衡节点执行右旋（双旋转）
• RL型（右左失衡）：失衡节点平衡因子为-2，其右子节点平衡因子为+1 → 先对右子节点执行右旋，再对失衡节点执行左旋（双旋转）

关于插入节点2后的双旋转问题 #

你提到的场景里，核心判断错误出在平衡因子的符号一致性上：
假设插入节点2后，失衡节点是5，其平衡因子为-2（右子树比左子树高2），而它的右子节点3的平衡因子为+1（左子树比右子树高1）——此时失衡节点的失衡方向（右）与子节点的失衡方向（左）符号相反，属于RL型失衡，必须用双旋转才能让树恢复平衡。

如果直接用单旋转（左旋5），旋转后的树依然会存在平衡因子超标的节点，无法满足AVL树的要求。只有先右旋节点3修正子树的失衡方向，再左旋节点5，才能让整棵树的所有节点平衡因子回到合法范围内。

你之前误以为两者符号相同，本质是对平衡因子的计算方向或节点的层级关系判断有误，记住：父节点与子节点失衡方向相同时用单旋转，相反时必须用双旋转。

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