algorithm - 平衡 AVL 树

Question

我在处理平衡 AVL 树问题时遇到了麻烦，因为我的解决方案似乎与教科书后面的解决方案相冲突。我查看了 AVL 树的在线可视化，他们认为我的是正确的。我的课本错了吗？

这是树：

然后我必须将 65 插入到这个 AVL 树中。这会导致不平衡，据我了解，需要左右旋转。

这是我想出的，并已通过http://robinsswei.github.io/VisGraphs/avltree.html确认：

这是我的教科书所说的正确答案：

哪一个是正确答案？

Answer 1

嘿，我实际上认为这两种解决方案都是正确的。我认为你的书可能会有不同的原因有几个。插入节点后，你会发现 2 个不同的节点的平衡因子为 2。那是节点 34 和 45。该算法的工作原理是在插入之后，它沿着返回根节点的路径检查平衡因子以及更新它们的节点高度。我认为，因为根是最后被访问并标记为轮换的，这就是它这样做的原因。另一个潜在的原因是，对于根节点，旋转只需要一个简单的旋转，而您所做的旋转需要一个双重旋转。无论如何，我觉得两个答案都足够了。

我将尝试为那些可能不知道 AVL 树是什么的人解释这个问题。我也试着给这个例子贴上标签。您要做的第一件事是在插入新节点之前确保您的起始 AVL 树满足要求。我只需标记每个节点的高度，然后获取每个父节点的子节点的高度差。

AVL 树要求每个节点的左右子节点的高度最多相差 +1 或 -1。(-1,0,1)

例如在第一张图中，在插入之前，Id 从下到上开始。节点 87 没有任何子节点，这将是 0。节点 45 只有一个子节点，因此我们计算 87 的 0 高度。节点 3 没有子节点，所以这也是 0。节点 34 有两个孩子，3 和 45。他们的区别只有 1。所有节点都通过了 AVL Tree 测试。

接下来只需像二叉搜索树一样遍历它来插入节点。

插入后重新标记节点的高度，并为每个节点再次比较它们。这次我们看到节点 34（我们的根节点）在孩子（2-0）之间有一个“2”的差异。我们现在知道节点 34 需要旋转。
执行简单的左旋转并满足 AVL 属性。

Answer 2

以 45 为根的第二个是正确答案。平衡的 AVL 树必须有两个子长度（深度）相同。所以进入65后，你的树就会不平衡。所以你需要将节点向左移动。

Answer 3

我认为应该是左右旋转而不是左右旋转，所以教科书是对的。