首页 文章

这个二叉树可以 balancer 吗？

提问于
浏览 次
1

我试图实现代码来实现 balancer 二进制搜索树的方式（强力），我发现有一个（树的）情况，似乎它无法 balancer . 树是

6
          \
           10
          /
         8
        / \
       7   9

你可以明显地发现这棵树的正确高度比它的左高度大得多，所以我绕着'6'左转树，然后新的树将是

10
      /
     6
      \
       8
      / \
     7   9

然后它变成左高度远大于它的右高度，所以在下一步中我必须在节点'10'周围向右（向后）旋转树 .

似乎必须有一个无限循环来围绕它的根节点旋转这个树（旋转左，右，左，右......等），同时 balancer 这棵树 . 有 balancer 这棵树的解决方案吗？

binary-tree

2 回答

  • 2

    您不应该首先围绕根旋转，而应首先旋转右子树，因为它也是不 balancer 的 .

    这个

    10
      /
     8
    / \
   7   9

    应该旋转并转换为

    8
    / \
   7   10
      /
     9

    然后树就会

    6
    \
     8
    / \
   7   10
      /
     9

    然后你绕着根旋转

    8
   / \
  6   10
   \   /
    7 9
    回复于
  • 1

    最简单的算法是：

    • 在此树中连续3个节点（在您的情况下为6,8,10）

    • 订购那些节点

    • 依次附加原始子树：空，7,9，空

    这会产生：

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

    这棵树很 balancer .

    回复于

相关问题