删除节点后，如何更新受影响子树节点的平衡因子及处理旋转影响？

一、删除后的平衡因子回溯更新逻辑 #

删除节点会导致某条路径的节点数减少，需要从删除节点的父节点开始向上遍历祖先节点，逐个更新平衡因子：

• 若删除的是当前节点左子树中的节点：当前节点的balancefactor减1（左子树高度相对降低，平衡因子向右侧倾斜）
• 若删除的是当前节点右子树中的节点：当前节点的balancefactor加1（右子树高度相对降低，平衡因子向左侧倾斜）

每更新一个节点后，根据新的平衡因子判断后续操作：

• 若balancefactor变为0：当前节点高度无变化，无需继续向上回溯（上层节点的平衡因子不受影响）
• 若balancefactor变为±1：当前节点高度改变，需继续向上更新父节点
• 若balancefactor变为±2：节点失衡，执行旋转修复，修复后停止回溯（旋转会恢复平衡，且不会影响更上层节点的高度）

二、旋转操作的平衡因子修正规则 #

因为你的节点直接存储balancefactor而非高度，旋转时可直接基于当前节点的平衡因子值修正，无需计算高度：

1. 左旋转（修复右右失衡） #

设失衡节点为A，其右子节点为B：

• A.balancefactor = A.balancefactor - 1 - max(B.balancefactor, 0)
• B.balancefactor = B.balancefactor - 1 + min(A.balancefactor, 0)

2. 右旋转（修复左左失衡） #

设失衡节点为A，其左子节点为B：

• A.balancefactor = A.balancefactor + 1 - min(B.balancefactor, 0)
• B.balancefactor = B.balancefactor + 1 + max(A.balancefactor, 0)

3. 左右旋转（修复左右失衡） #

先对A的左子节点B执行左旋转，修正B和其右子节点C的平衡因子；再对A执行右旋转，按右旋转规则修正A和C的平衡因子。

4. 右左旋转（修复右左失衡） #

先对A的右子节点B执行右旋转，修正B和其左子节点C的平衡因子；再对A执行左旋转，按左旋转规则修正A和C的平衡因子。

三、核心注意事项 #

• 回溯更新必须严格遵循“从删除节点父节点向上”的顺序，不能跳过任何节点，否则会导致平衡因子错乱
• 上述旋转修正公式完全适配直接存储balancefactor的节点结构，无需额外维护高度变量
• 当节点平衡因子更新为0时，必须停止回溯——此时当前节点高度与删除前一致，上层节点的平衡因子不会发生变化

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