algorithm - AVL 树再平衡算法：如何在 Zig-Zig 和 Zig-Zag 情况之间做出决定？

Question

我正在尝试将 AVL 树作为一种实践来实现。对于插入和删除操作，我的实现首先执行正常的 BST 插入和删除，然后沿着父链检查和修复任何不平衡的子树。但是，当不平衡节点的子节点的平衡因子为 0 时，我不确定如何在 zig-zig 和 zig-zag 情况之间做出决定。我想在这种情况下我可以选择任何一个，但这并不为删除工作。

假设树看起来像这样，我想删除 78，

再平衡方法会走到 70（根），发现它不平衡，那么问题来了：因为 44 的平衡因子为 0，我应该在 70-44-33 上执行 Zig-zig 案例，还是 Zig 70-44-48 上的 -zag 案例？

后者将无法平衡树。围绕 44 的左旋转，然后围绕 70 的右旋转将产生以下结果：

另一方面，zig-zig 案例（70 左右的右旋转）是正确的方法：

标签： algorithmdata-structuresbinary-treeavl-tree

Answer 1

在 AVL 树中使用“zig zag”术语是不寻常的。该术语对于 Splay 树（也是平衡树）更为常见，其目的是通过旋转将特定节点冒泡到顶部。AVL 树中没有这样的目的。AVL 树的术语包括简单旋转（从左到右，反之亦然）和双旋转（两个简单旋转的组合）。

当删除一个节点后，您在树中向上移动并发现平衡违规，这意味着该节点中临时更新的平衡因子为 -2 或 2。

如果较重的孩子的平衡因子具有相反的符号（因此，当其不平衡的父母有 -2 时为 1；或当其不平衡的父母有 2 时为 -1），则需要双重旋转。在所有其他情况下，需要进行简单的旋转。

这里描述了需要双重旋转的内重孙子的情况（复制自维基百科）：

在您的示例中，节点 44 的平衡因子为 0，因此不需要双重旋转，您应该只从左到右旋转根。如果我们想象同一棵树，但没有节点 31 和 34（使 33 成为叶子），那么 44 处的平衡因子将为 1（与 70 处的 -2 相反）并且需要进行双重旋转。