如何判断二叉树是否平衡？

Question

那些学年已经有一段时间了。在一家医院找到了一份 IT 专家的工作。现在正尝试着去做一些实际的编程。我现在正在研究二叉树，我想知道确定树是否高度平衡的最佳方法是什么。

我在想一些事情：

 public boolean isBalanced(Node root){
    if(root==null){
        return true;  //tree is empty
    }
    else{
        int lh = root.left.height();
        int rh = root.right.height();
        if(lh - rh > 1 || rh - lh > 1){
            return false;
        }
    }
    return true;
}

这是一个好的实现吗？还是我错过了什么？

原文由 user69514 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

在搜索其他内容时偶然发现了这个老问题。我注意到您从未得到完整的答案。

解决这个问题的方法是首先为您要编写的函数编写规范。

规范：如果 (1) 它为空，或 (2) 它的左右子树高度平衡且左树的高度在 1右树的高度。

现在您有了规范，编写代码就很简单了。只需遵循规范：

 IsHeightBalanced(tree)
    return (tree is empty) or
           (IsHeightBalanced(tree.left) and
            IsHeightBalanced(tree.right) and
            abs(Height(tree.left) - Height(tree.right)) <= 1)

将其翻译成您选择的编程语言应该是微不足道的。

额外练习：这个天真的代码草图在计算高度时遍历树的次数太多了。你能让它更有效率吗？

超级奖励练习：假设这棵树非常 _不平衡_。就像，一侧有 100 万个节点，另一侧有 3 个节点。是否存在该算法炸毁堆栈的场景？您能否修复实现，使其永远不会炸毁堆栈，即使给定的树非常不平衡？

更新：Donal Fellows 在他的回答中指出，人们可以选择不同的“平衡”定义。例如，可以采用更严格的“高度平衡”定义，并要求到 最近的 空孩子的路径长度在到 最远 空孩子的路径之一之内。我的定义没有那么严格，因此允许更多的树。

一个也可以没有我的定义那么严格；可以说，平衡树是这样一棵树，其中到每个分支上的空树的最大路径长度相差不超过 2、3 或某个其他常数。或者最大路径长度是最小路径长度的一部分，比如一半或四分之一。

平时真的无所谓。任何树平衡算法的要点都是确保您不会在一侧有一百万个节点而另一侧有三个节点的情况下结束。 Donal 的定义在理论上很好，但在实践中，提出满足该严格级别的树平衡算法是一件痛苦的事情。性能节省通常不能证明实施成本是合理的。您花费大量时间进行不必要的树重新排列，以达到在实践中几乎没有什么不同的平衡水平。谁在乎有时需要 40 个分支才能到达百万节点不完全平衡树中最远的叶子，而理论上完全平衡的树只需要 20 个？关键是它永远不需要一百万。从最坏的一百万降到最坏的四十通常就足够了；您不必一直走到最佳情况。

原文由 Eric Lippert 发布，翻译遵循 CC BY-SA 3.0 许可协议