AVL树平衡
给定下面的 AVL 树：
23
/ \
19 35
/ \ / \
8 20 27 40
/
38
/
36
只在 40 度向右旋转一次可以吗？使它像这样：
23
/ \
19 35
/ \ / \
8 20 27 38
/ \
36 40
它仍然符合 AVL 属性，即与左子树相比具有 -+1 高度。
在答案中，它进行了双重旋转，因此上面 35 处的子树将如下所示：
23
/ \
19 38
/ \ / \
8 20 35 40
/ \
27 36
我不明白何时进行双重旋转以及何时进行单次旋转（如果它们都不违反 height 属性）。
Given an AVL tree below:
23
/ \
19 35
/ \ / \
8 20 27 40
/
38
/
36
Is it ok to just do a single rotation at 40, to the right? Making it something like this:
23
/ \
19 35
/ \ / \
8 20 27 38
/ \
36 40
It still conforms tot he AVL property of having -+1 height compared to the left subtree.
In the answer it does a double rotation so the subtree at 35 above would look like this after:
23
/ \
19 38
/ \ / \
8 20 35 40
/ \
27 36
I don't understand when to do a double rotation and when to do a single rotation if they both do not violate the height property.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
双旋转可能是由于使用了特定的 AVL 算法所致。对我来说，这两个答案看起来都是有效的 AVL 树。
The double rotation may be due to a specific AVL algorithm in use. Both answers look like valid AVL trees to me.
如果原始问题仅给出不平衡 AVL 树（而不是添加或删除节点之前的平衡树），则单次旋转是有效答案。
如果问题提供了添加或删除节点之前和的 AVL 树，则重新平衡算法可能会导致发生双重旋转。
If the original question was given with only the unbalanced AVL tree (and not the balanced tree before a node was added or removed), then the single rotation is a valid answer.
If the question provides the AVL tree before and after a node was added or removed, then the algorithm for rebalancing could result in the double rotation occurring.
两个答案都是正确的，尽管根据我使用的文献：
根据这些规则，平衡因子变为 2 的最近祖先是
40在你的例如，插入是在40的左子树的左子树中进行的，因此您必须执行 LL 旋转。遵循这些规则，您的第一个答案将是所选的操作。尽管如此，这两个答案都是正确的，并且取决于您使用的算法及其遵循的规则。
Both answers are right, though according to the literature that I use:
According to these rules, the nearest ancestor whose balance factor becomes 2 is
40in your example, and the insertion was made in the left subtree of the left subtree of40so you have to perform an LL rotation. Following these rules, the first of your answers will be the chosen operation.Still, both answers are correct and depends of the algorithm you are using and the rules it follows.