AVL Tree 重新平衡算法：如何在 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，
rebalancing方法走到70（root），发现不平衡，问题来了：因为44的平衡系数是0，我应该在70-44-上做Zig-zig case吗？ 33，或 70-44-48 的锯齿形情况？
后者无法平衡树。左旋转 44 左右，然后右旋转 70 左右会产生以下结果：
另一方面，zig-zig 情况（右转约 70）是正确的方法：
在 AVL 树中使用“之字形”术语并不常见。该术语在 Splay 树（也是平衡树）中更为常见，其目的是通过旋转将特定节点冒泡到顶部。 AVL 树中没有这样的目的。 AVL 树的术语包括简单旋转（从左到右或从左到右）和双旋转（两个简单旋转的组合）。
当您在删除节点后在树中向上移动并发现平衡违规时，这意味着该节点中临时更新的平衡因子为 -2 或 2。
如果重边的子项具有相反符号的平衡因子（因此当其不平衡的父项具有 -2 时为 1；或当其不平衡的父项具有 2 时为 -1），则需要进行双重旋转。在所有其他情况下，需要进行简单的旋转。
内重孙子的情况，需要双轮转，如下图（复制自Wikipedia）：
在您的示例中，节点 44 的平衡因子为 0，因此不需要进行二次旋转，您只需将根节点从左向右旋转即可。如果我们想象同一棵树，但没有节点 31 和 34（使 33 成为一片叶子），那么 44 处的平衡因子将为 1（与 70 处的 -2 的符号相反）并且需要进行两次旋转。
我正在尝试实现 AVL 树作为练习。对于插入和删除操作，我的实现首先进行正常的 BST 插入和删除，然后沿着父链向上走以检查和修复任何不平衡的子树。但是，当不平衡节点的子节点的平衡因子为 0 时，我不确定如何在 zig-zig 和 zig-zag 情况之间做出决定。我认为在这种情况下我可以选择其中之一，但这不是删除工作。
假设树看起来像这样，我想删除 78，
rebalancing方法走到70（root），发现不平衡，问题来了：因为44的平衡系数是0，我应该在70-44-上做Zig-zig case吗？ 33，或 70-44-48 的锯齿形情况？
后者无法平衡树。左旋转 44 左右，然后右旋转 70 左右会产生以下结果：
另一方面，zig-zig 情况（右转约 70）是正确的方法：
在 AVL 树中使用“之字形”术语并不常见。该术语在 Splay 树（也是平衡树）中更为常见，其目的是通过旋转将特定节点冒泡到顶部。 AVL 树中没有这样的目的。 AVL 树的术语包括简单旋转（从左到右或从左到右）和双旋转（两个简单旋转的组合）。
当您在删除节点后在树中向上移动并发现平衡违规时，这意味着该节点中临时更新的平衡因子为 -2 或 2。
如果重边的子项具有相反符号的平衡因子（因此当其不平衡的父项具有 -2 时为 1；或当其不平衡的父项具有 2 时为 -1），则需要进行双重旋转。在所有其他情况下，需要进行简单的旋转。
内重孙子的情况，需要双轮转，如下图（复制自Wikipedia）：
在您的示例中，节点 44 的平衡因子为 0，因此不需要进行二次旋转，您只需将根节点从左向右旋转即可。如果我们想象同一棵树，但没有节点 31 和 34（使 33 成为一片叶子），那么 44 处的平衡因子将为 1（与 70 处的 -2 的符号相反）并且需要进行两次旋转。