关于AVL旋转

Question

我阅读有关数据结构和算法AVL树由马克·艾伦Wesis

假设节点重新平衡是X.有4例，我们 可能必须解决（两个是其他两个镜像）： 插入X的左侧子树的左侧子树中，插入 X的左侧子树的右侧子树，右侧子树的 子树中的插入X ，或在X的右侧子树的右子树 中插入。

平衡通过树轮旋转恢复。

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

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

感谢

Answer 1

假设要插入的节点是一书中说，有4例。让我们以一个在那里我是X的左子的左子：

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

“镜子”的，这是当我是X的右孩子的右子：

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

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

至于你的第二个问题，这个想法是一样的。在对称情况下（即镜像情况），您可以进行相同的旋转，只需左右颠倒即可。