如何判断二叉树是否平衡? [英] How to determine if binary tree is balanced?

问题描述

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

It's been a while from those school years. Got a job as IT specialist at a hospital. Trying to move to do some actual programming now. I'm working on binary trees now, and I was wondering what would be the best way to determine if the tree is height-balanced.

我在想一些事情:

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;
}

这是一个很好的实现吗?还是我遗漏了什么?

Is this a good implementation? or am I missing something?

推荐答案

在搜索其他内容时偶然发现了这个老问题.我注意到你从来没有得到一个完整的答案.

Stumbled across this old question while searching for something else. I notice that you never did get a complete answer.

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

The way to solve this problem is to start by writing a specification for the function you are trying to write.

规范:如果(1)它是空的，或者(2)它的左右孩子高度平衡并且左树的高度在1 右树的高度.

Specification: A well-formed binary tree is said to be "height-balanced" if (1) it is empty, or (2) its left and right children are height-balanced and the height of the left tree is within 1 of the height of the right tree.

既然您有了规范，编写代码就很简单了.只需遵循规范:

Now that you have the specification, the code is trivial to write. Just follow the specification:

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

将其翻译成您选择的编程语言应该很简单.

Translating that into the programming language of your choice should be trivial.

额外练习:这个简单的代码草图在计算高度时遍历树的次数太多了.你能让它更有效率吗?

Bonus exercise: this naive code sketch traverses the tree far too many times when computing the heights. Can you make it more efficient?

超级奖励练习:假设树大量不平衡.比如，一侧深一百万个节点，另一侧深三个节点.是否存在该算法炸毁堆栈的情况?您能否修复实现，使其永远不会破坏堆栈，即使是在给定一个严重不平衡的树的情况下?

Super bonus exercise: suppose the tree is massively unbalanced. Like, a million nodes deep on one side and three deep on the other. Is there a scenario in which this algorithm blows the stack? Can you fix the implementation so that it never blows the stack, even when given a massively unbalanced tree?

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

UPDATE: Donal Fellows points out in his answer that there are different definitions of 'balanced' that one could choose. For example, one could take a stricter definition of "height balanced", and require that the path length to the nearest empty child is within one of the path to the farthest empty child. My definition is less strict than that, and therefore admits more trees.

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

One can also be less strict than my definition; one could say that a balanced tree is one in which the maximum path length to an empty tree on each branch differs by no more than two, or three, or some other constant. Or that the maximum path length is some fraction of the minimum path length, like a half or a quarter.

通常真的无所谓.任何树平衡算法的重点是确保您不会遇到一侧有 100 万个节点而另一侧有 3 个节点的情况.Donal 的定义在理论上很好，但在实践中，提出一个满足这种严格程度的树平衡算法是很痛苦的.性能节省通常不能证明实现成本是合理的.您花费大量时间进行不必要的树重新排列，以达到在实践中几乎没有区别的平衡水平.谁会在乎有时需要四十个分支才能到达一百万个节点的不完全平衡树中的最远叶子，而在理论上它在一个完美平衡的树中只需要二十个?关键是它永远不需要一百万.从最坏的一百万下降到最坏的四十通常已经足够了.您不必一直走到最佳情况.

It really doesn't matter usually. The point of any tree-balancing algorithm is to ensure that you do not wind up in the situation where you have a million nodes on one side and three on the other. Donal's definition is fine in theory, but in practice it is a pain coming up with a tree-balancing algorithm that meets that level of strictness. The performance savings usually does not justify the implementation cost. You spend a lot of time doing unnecessary tree rearrangements in order to attain a level of balance that in practice makes little difference. Who cares if sometimes it takes forty branches to get to the farthest leaf in a million-node imperfectly-balanced tree when it could in theory take only twenty in a perfectly balanced tree? The point is that it doesn't ever take a million. Getting from a worst case of a million down to a worst case of forty is usually good enough; you don't have to go all the way to the optimal case.

这篇关于如何判断二叉树是否平衡?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！