这个二叉树能平衡吗？

Question

我曾试图实现代码来实现平衡二叉搜索树的方式（蛮力），我发现有一个案例（树），似乎无法平衡。这棵树是

         6
          \
           10
          /
         8
        / \
       7   9

你可以明显地发现，这棵树的右边高度比它的左边高度大得多，所以我绕着'6'向左旋转，那么新树就会

       10
      /
     6
      \
       8
      / \
     7   9

然后，左边的高度比右边的高度大得多，所以在下一步中，我必须围绕节点“10”向右（返回）旋转树。

似乎必须有一个无限循环来旋转这棵树围绕它的根节点（旋转左、右、左、右……以此类推），同时平衡这棵树。平衡这棵树有解决方案吗？

Answer 1

最简单的算法是:

1. 在此树中取3个连续节点（在您的情况下为6,8,10）
2. 排序那些节点
3. 按顺序附加原始子树：空、7、9、空

这将产生：

     8
   /   \
  6     10
 / \   /  \
.   7 9    .

这棵树非常平衡。

Answer 2

您不应该首先围绕根旋转，而应该首先旋转右侧子树，因为它也是不平衡的。

这

       10
      /
     8
    / \
   7   9

应该旋转并转换为

     8
    / \
   7   10
      /
     9

那么这棵树将会

   6
    \
     8
    / \
   7   10
      /
     9

然后你绕着根旋转

    8
   / \
  6   10
   \   /
    7 9