平衡 AVL 树
Balancing an AVL tree
我在平衡 AVL 树问题上遇到了麻烦，因为我的解决方案似乎与教科书后面的解决方案冲突。我查看了 AVL 树的在线可视化，他们认为我的是正确的。我的课本错了吗？
这是树：
然后我必须将 65 插入到这个 AVL 树中。这会导致不平衡，根据我的理解，需要左右旋转。
这是我想出的，并已通过 http://robinsswei.github.io/VisGraphs/avltree.html 确认：
下面是我的教科书所说的正确答案：
哪一个是正确答案？
嘿，
我实际上认为这两种解决方案都是正确的。我认为您的书可能有所不同的原因有几个。插入节点后，你会发现2个不同的节点的平衡因子为2。那是节点 34 和 45。该算法的工作原理是在插入后，它沿着这条路径回到根节点，检查平衡因子并更新它们的节点高度。我认为因为根最后一次被访问并被标记为轮换是它这样做的原因。另一个潜在的原因是，对于根节点，旋转只需要一个简单的旋转，而您所做的旋转需要两次旋转。无论如何，我觉得这两个答案都足够了。
我会尝试为那些可能不知道什么是 AVL 树的人解释这个问题。我也试图标记一个插图。您要做的第一件事是在插入新节点之前确保您的起始 AVL 树满足要求。我只会标记每个节点的高度，然后得到每个 children 节点的高度差 parent.
AVL树要求每个节点的左右children高度最多相差+1或-1。 (-1,0,1)
比如第一张图，在插入之前，我是从下往上开始的。节点 87 没有任何 children 到这将是 0。节点 45 只有一个 child 所以我们计算 87 的 0 高度。节点 3 没有 children，所以这也是 0。节点34有两个children，3和45，他们的差只有1。所有节点都通过了AVL Tree测试。
接下来只需像二叉搜索树一样遍历它来插入节点。
Re-label 插入后节点的高度，并再次比较每个节点。这次我们看到节点 34（我们的根节点）在 children(2-0) 之间有一个“2”的差异。我们现在知道节点 34 需要旋转。
执行简单的左旋转并满足 AVL 属性。
以45为根的第二个是正确答案。平衡的 AVL 树必须具有相同的子长度（深度）。所以输入65之后，你的树就会不平衡了。所以你需要将节点向左移动。
我觉得应该是左右旋转而不是左右旋转，所以课本上说的对
我在平衡 AVL 树问题上遇到了麻烦，因为我的解决方案似乎与教科书后面的解决方案冲突。我查看了 AVL 树的在线可视化，他们认为我的是正确的。我的课本错了吗？
这是树：
然后我必须将 65 插入到这个 AVL 树中。这会导致不平衡，根据我的理解，需要左右旋转。
这是我想出的，并已通过 http://robinsswei.github.io/VisGraphs/avltree.html 确认：
下面是我的教科书所说的正确答案：
哪一个是正确答案？
嘿， 我实际上认为这两种解决方案都是正确的。我认为您的书可能有所不同的原因有几个。插入节点后，你会发现2个不同的节点的平衡因子为2。那是节点 34 和 45。该算法的工作原理是在插入后，它沿着这条路径回到根节点，检查平衡因子并更新它们的节点高度。我认为因为根最后一次被访问并被标记为轮换是它这样做的原因。另一个潜在的原因是，对于根节点，旋转只需要一个简单的旋转，而您所做的旋转需要两次旋转。无论如何，我觉得这两个答案都足够了。
我会尝试为那些可能不知道什么是 AVL 树的人解释这个问题。我也试图标记一个插图。您要做的第一件事是在插入新节点之前确保您的起始 AVL 树满足要求。我只会标记每个节点的高度，然后得到每个 children 节点的高度差 parent.
AVL树要求每个节点的左右children高度最多相差+1或-1。 (-1,0,1)
比如第一张图，在插入之前，我是从下往上开始的。节点 87 没有任何 children 到这将是 0。节点 45 只有一个 child 所以我们计算 87 的 0 高度。节点 3 没有 children，所以这也是 0。节点34有两个children，3和45，他们的差只有1。所有节点都通过了AVL Tree测试。
接下来只需像二叉搜索树一样遍历它来插入节点。
Re-label 插入后节点的高度，并再次比较每个节点。这次我们看到节点 34（我们的根节点）在 children(2-0) 之间有一个“2”的差异。我们现在知道节点 34 需要旋转。
执行简单的左旋转并满足 AVL 属性。
以45为根的第二个是正确答案。平衡的 AVL 树必须具有相同的子长度（深度）。所以输入65之后，你的树就会不平衡了。所以你需要将节点向左移动。
我觉得应该是左右旋转而不是左右旋转，所以课本上说的对