提问人：dw218192 提问时间：10/31/2021 最后编辑：trincotdw218192 更新时间：10/31/2021 访问量：734
AVL 树再平衡算法：如何在 Zig-Zig 和 Zig-Zag 情况之间做出决定？
AVL Tree rebalancing algorithm: how to decide between Zig-Zig and Zig-Zag cases?
问：
我正在尝试将 AVL 树作为一种实践来实现。对于插入和删除操作，我的实现首先执行正常的 BST 插入和删除，然后沿着父链向上检查并修复任何不平衡的子树。但是，当不平衡节点的子节点的平衡因子为 0 时，我不确定如何在 zig-zig 和 zig-zag 情况之间做出决定。我以为在这种情况下我可以选择任何一个，但这不适用于删除。
假设这棵树看起来像这样，我想删除 78，
再平衡方法会走到 70（根），发现它不平衡，那么问题来了：因为 44 的平衡因子为 0，我应该在 70-44-33 上执行 Zig-zig 情况，还是在 70-44-48 上执行 Zig-zig 情况？
后者将无法平衡树。在 44 左右左转，然后在 70 左右右转将产生以下结果：
另一方面，锯齿形情况（右旋 70 左右）是正确的方法：
答：
3赞
trincot
10/31/2021
#1
在 AVL 树中使用“之字形”术语是不寻常的。该术语在 Splay 树（也是平衡树）中更为常见，其目的是通过旋转将特定节点冒泡到顶部。AVL 树中没有这样的目的。AVL 树的术语包括简单旋转（从左到右，反之亦然）和双旋转（两个简单旋转的组合）。
当您在删除节点后在树中向上移动并发现余额违规时，这意味着该节点中临时更新的余额因子为 -2 或 2。
如果重侧的子项的平衡因子具有相反的符号（因此，当其不平衡的父项为 -2 时为 1;当其不平衡的父项为 2 时为 -1），则需要双重旋转。在所有其他情况下，都需要进行简单的旋转。
这里描述了需要双重旋转的内重孙子的情况（复制自维基百科）：
在您的示例中，节点 44 的平衡因子为 0，因此不需要双旋转，您只需从左向右旋转根即可。如果我们想象同一棵树，但没有节点 31 和 34（使 33 成为一片叶子），那么 44 处的平衡因子将是 1（与 70 处的 -2 相反），并且需要双旋转。
评论