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 )，这可能是您能获得的最有效的方法，因为您必须检查树中的每个节点才能测试平衡条件，并且该算法会精确地查看每个节点一次。