algorithm - 找到必须添加以使二叉树平衡的最小节点数？

Question

假设给定一棵任意二叉树。如果所有节点都满足以下条件，我们将称树平衡：

1. 该节点是叶子，或者
2. 左子树的高度和右子树的高度最多相差±1，左右子树本身是平衡的。

是否有一种有效的算法来确定需要添加到树中以使其平衡的最小节点数？为简单起见，我们假设节点只能作为叶节点插入（就像将节点插入到不进行重新平衡的二叉搜索树中的方式一样）。

Answer 1

以下树符合您的定义，尽管它对我来说似乎不是很平衡：

编辑这个答案是错误的，但它有足够有趣的东西，我不想删除它。该算法产生一棵平衡树，但不是最小的。它添加的节点数为：

其中n范围在树中的所有节点上，lower(n)是深度n较低的孩子的深度，upper(n)是深度较高的孩子的n深度。k利用第一个斐波那契数的和是 的事实fib(k+2)-1，我们可以用 替换内部和fib(upper(n)) - fib(lower(n) + 2)。

该公式（或多或少）源自以下算法，用于将节点添加到树中，使其平衡（在python中，仅显示相关算法）：

def balance(tree, label):
  if tree is None:
    return (None, 0)
  left, left_height = balance(tree.left_child, label)
  right, right_height = balance(tree.right_child, label)
  while left_height < right_height - 1:
    left = Node(label(), left, balanced_tree(left_height - 1, label))
    left_height += 1
  while right_height < left_height - 1:
    right = Node(label(), right, balanced_tree(right_height - 1, label))
    right_height += 1
  return (Node(tree.label, left, right), max(left_height, right_height) + 1)

def balanced_tree(depth, label):
  if depth <= 0:
    return None
  else:
    return Node(label(),
                balanced_tree(depth - 1, label),
                balanced_tree(depth - 2, label))

根据要求：报告计数而不是创建树：

def balance(tree):
  if tree is None:
    return (0, 0)
  left, left_height = balance(tree.left_child)
  right, right_height = balance(tree.right_child)
  while left_height < right_height - 1:
    left += balanced_tree(left_height - 1) + 1
    left_height += 1
  while right_height < left_height - 1:
    right += balanced_tree(right_height - 1) + 1
    right_height += 1
  return (left + right, max(left_height, right_height) + 1)

def balanced_tree(depth):
  if depth <= 0:
    return 0
  else:
    return (1 + balanced_tree(depth - 1)
              + balanced_tree(depth - 2))

编辑：实际上，我认为除了更有效地计算深度为 n 的最小平衡树的大小（即记忆它，或使用封闭形式：它只是fibonacci(n+1)-1）之外，这可能是你能得到的最有效的，因为你必须检查树中的每个节点以测试平衡条件，并且该算法精确地查看每个节点一次。

Answer 2

这行得通吗？

从顶部递归。如果节点 A 不平衡，则在短边添加节点 B，并在节点 B 中添加足够的左侧节点，直到节点 A 平衡。

（当然，计算添加的节点。）

Answer 3

首先让我们找到每个节点的左孩子和右孩子的高度。

现在考虑树的根，它的高度是

1+max(height(root.left) , height(root.right)).

让我们假设左边的高度为 n-1，那么右边的最小高度应为 n-2。让我们在这里定义另一个关系req[node] -> 每个节点的最小所需高度以使树平衡。

如果您观察到一个节点的高度h，它的一个孩子应该至少在 n-1 并且为了使其平衡，其他孩子应该至少是 n-2。

从根开始req[root] = 根的高度

伪代码是：

    def chk_nodes(root, req):

      if(root == NULL):
        return minNodes(req)

      if(left[root] > right[root]):
       return chk_nodes(root.left  , req-1) + chk_nodes(root.right , req-2)

      else return chk_nodes(root.left , req-2) + chk_nodes(root.right , req-1)

现在什么是 minNodes(int req)？

它是一个返回'创建高度为 h 的平衡二叉树所需的最小节点数'的函数。该功能非常直观且不言自明。

      def minNodes(int req) :
          if req < 0 : return 0
          return 1 + minNodes(req-1) + minNodes(req-2)

在 minNodes 函数中，可以使用查找表使其查找时间为 O(1)，构建时间为 O(N)。

当 chk_nodes 函数递归运行时，在叶节点处，我们将剩下 left-node ， req 。如果那个 req > 0 那么应该有一个高度 req 的新子树（平衡）。因此，在这个特定的叶节点处需要 minNodes( req )。

只需 2 次遍历和O(N)时间，O(N)空间问题就解决了。