关于AVL树单节点删除是否需两次双旋转的技术问询

你的判断完全正确：删除单个节点后，AVL树的重平衡过程最多只需要一次双旋转（或单旋转），不可能出现需要两次双旋转的情况。

核心逻辑验证 #

• 不平衡的传播特性：删除节点只会导致从删除点到根节点的单条路径上的节点高度可能变化，不平衡只会沿这条路径向上传播。一旦某节点（记为Z）被重新平衡后，其子树的高度会恢复到删除前的状态，这就阻断了高度变化继续向上传递，祖先节点的平衡因子不会再受到影响。
• 双旋转的作用效果：当触发双旋转（左-右或右-左）时，旋转操作会同时修正Z节点及其子节点的平衡因子，并且让Z所在子树的高度回到删除操作前的水平。这意味着Z的父节点的平衡因子不会因为这次删除操作而改变，自然不需要再对上层节点进行任何旋转操作。

为什么不存在两次双旋转的场景 #

假设存在需要两次双旋转的情况，意味着第一次旋转后，上层祖先节点又出现了平衡因子为±2的情况，但这是不可能的：

1. 第一次旋转（无论单/双）已经修复了路径上第一个不平衡节点的子树高度，上层节点的平衡因子依赖的子树高度没有发生变化，因此不会出现新的不平衡。
2. AVL树的删除重平衡逻辑中，只需要从删除节点开始向上遍历，找到第一个不平衡节点进行修复即可，修复后遍历直接终止，不会继续向上检查。

总结 #

单节点删除操作引发的不平衡，只会在从删除点到根的路径上出现至多一个需要修复的不平衡节点，该节点最多需要一次单旋转或双旋转即可修复，不会出现需要多次双旋转的场景。

内容的提问来源于stack exchange，提问作者劉宸瑋