如何确定是否二叉树是平衡的？ [英] 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.

现在，你有规范，在code是微不足道的编写。只要按照规范的：

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.

奖金锻炼：计算高度时，这个天真code草图遍历树太多次。你可以使它更有效率？

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?

更新：多纳尔研究员指出，在他的回答，有对均衡，人们可以选择不同的定义。例如，一种可以采取的高度平衡更严格的定义，并要求该路径长度向的最接近的空子是内的路径向的最远的空单儿童。我的定义是低于这个水平严格，因此承认更多的树。

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.

你也可以比我的定义那样严格;人们可以说，平衡树是其中的最大路径长度为空树的每个分支的差异不超过两个，或三个，或一些其它常数。或者说，最大路径长度为某个分数最小路径长度的，像一个半或四分之一。

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.

这其实并不重要，通常。任树平衡算法的一点是要确保你不拉闸的情况下，你必须一边和上三一百万节点。敦尔的定义是细于理论，但在实践中它是一种痛苦上来与树均衡算法符合严格的那个水平。性能节省通常并不能证明实施成本。你花了很多时间做不必要的树重排，以达到平衡，实际上差别不大的水平。如果有时需要40枝去的最远的叶一百万个节点不完全平衡树时，它在理论上可以在一个完美的平衡树只有二十拿谁在乎呢？的一点是，它不会以往采取一百万。获取从一百万到四十一个最坏的情况下，最坏的情况是通常不够好;不必对所有的方式去最佳情况。

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屋！