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

Question

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

假设这棵树是这样的，我想删除78，

​

重新平衡方法会走到70 (根)，发现它不平衡，然后问题来了:因为44的平衡因子为0，我应该在70-44-33上执行Zig-zig案例，还是在70-44-48上执行Zig-zag案例？

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

​

另一方面，zig-zig型情况(在70左右右旋转)是正确的方法：

​

Answer 1

在AVL树中使用“zag”术语是不常见的。该术语更常见于展开树(也称为平衡树)，其目的是通过旋转将特定节点冒泡到顶部。在AVL树中没有这样的目的。AVL树的术语包括简单旋转(从左到右或从右到左)和双重旋转(两个简单旋转的组合)。

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

如果较重一侧的子项的平衡因子具有相反的符号(因此，当其不平衡的父项为-2时为1；或当其不平衡的父项为2时为-1 )，则需要进行两次旋转。在所有其他情况下，都需要简单的旋转。

内部重孙子的情况，需要两次旋转，如下所示(从Wikipedia复制)：

​

​

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