我试图实现代码来实现平衡二叉搜索树的方式（蛮力），并且我发现有一个（树的）情况，它似乎不能平衡。树是这个二叉树可以平衡吗？
6
\
10
/
8
/\
7 9
可以很明显的发现，这个树的右侧高度比左高度大得多，所以我向左旋转周围的树“6”，那么新的树会
10
/
6
\
8
/\
7 9
然后它变成左边的高度比右边的高度大得多，所以在下一步中我必须向右旋转（返回）节点'10'周围的树。
在平衡此树时，似乎必须有一个无限循环来绕着它的根节点旋转此树（旋转左，右，左，右...等等）。有没有解决这个树的解决方案？
你不应该首先围绕根旋转，而应该首先旋转右边的子树，因为它也是不平衡的。
这
10
/
8
/\
7 9
应旋转，并转换为
8
/\
7 10
/
9
那棵树会
6
\
8
/\
7 10
/
9
然后你身边根旋转
8
/\
6 10
\ /
7 9
非常感谢你！我发现我很尴尬！这是一个很好的解释！ –
对不起，杰里，我面对另一个二叉搜索树，1 - > 3 - > 2，我试图平衡这棵树（实际上它是一棵子树），但它被卡在一个循环。是否有可能平衡该二叉搜索树？ –
@DavidHsu，这是一种情况，你需要先旋转3> 2，然后把2放到根（双旋转）。我建议你阅读一些自学平衡二叉搜索树的标准实现的教科书。一个常见的实现是AVL树，你可以在这里参考https://en.wikipedia.org/wiki/AVL_tree的wikipage。双轮案例正是你在这里遇到的。 –
这样做的最简单的算法是：
这将产生：
8
/ \
6 10
/\ /\
. 7 9 .
这棵树非常平衡。
非常感谢你！我发现我很尴尬！这是一个很好的解释！ –
然后请upvote我的答案。 –
查看最大堆或最小堆。这可能会帮助你学习如何创建一个平衡的二叉树。 – denis