algorithm - 关于 AVL 旋转

Question

我正在阅读 Mark Allen Wesis 的数据结构和算法中的 AVL 树

假设要重新平衡的节点是 X。我们可能需要修复 4 种情况（其中两种是另外两种的镜像）： X 的左子树的左子树中的插入，右子树中的插入X 的左子树的插入，X 的右子树的左子树中的插入，或 X 的右子树的右子树中的插入。

通过树木旋转恢复平衡。

以下是我对上述文本片段的问题。

1. 作者所说的其他两个镜像是什么意思？
2. 什么是单旋转和双旋转的对称情况？

谢谢

Answer 1

假设要插入的节点是 I。书上说有 4 种情况。让我们以我是 X 的左孩子的左孩子为例：

    X
   / \
  ?   ?
 / \ / \
I  ? ?  ?

这个“镜像”是当我是 X 的右孩子的右孩子时：

    X
   / \
  ?   ?
 / \ / \
?  ? ?  I

这是一个“镜子”的原因是你必须为这两种情况做的旋转是相同的，只是左右颠倒了。其他两种情况也是如此，其中 I 是 X 的右孩子的左孩子，而 I 是 X 的左孩子的右孩子。

至于你的第二个问题，思路是一样的。在对称情况下（即镜面情况），您进行相同的旋转，只是左右颠倒。