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

How to determine if binary tree is balanced?

提问by user69514

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.

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

I was thinking of something along this:

我在想一些事情：

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?

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

回答by Jesse Rusak

This only determines if the top level of the tree is balanced. That is, you could have a tree with two long branches off the far left and far right, with nothing in the middle, and this would return true. You need to recursively check the root.leftand root.rightto see if they are internally balanced as well before returning true.

这仅确定树的顶层是否平衡。也就是说，你可以有一棵树在最左边和最右边有两条长树枝，中间没有任何东西，这将返回 true。在返回 true 之前，您需要递归检查root.left和root.right查看它们是否在内部平衡。

回答by tpdi

Well, you need a way to determine the heights of left and right, and if left and right are balanced.

那么，你需要一种方法来确定左右的高度，以及左右是否平衡。

And I'd just return height(node->left) == height(node->right);

我只想 return height(node->left) == height(node->right);

As to writing a heightfunction, read: Understanding recursion

至于编写height函数，请阅读： 理解递归

回答by lothar

What kind of tree are you talking about? There are self-balancingtrees out there. Check their algorithms where they determine if they need to reorder the tree in order to maintain balance.

你说的是什么树？那里有自平衡树。检查他们的算法，确定他们是否需要重新排序树以保持平衡。

回答by Uri

Balancing usually depends on the length of the longest path on each direction. The above algorithm is not going to do that for you.

平衡通常取决于每个方向上最长路径的长度。上面的算法不会为你做到这一点。

What are you trying to implement? There are self-balancing trees around (AVL/Red-black). In fact, Java trees are balanced.

你想实现什么？周围有自平衡树（AVL/红黑）。事实上，Java 树是平衡的。

回答by Steven A. Lowe

If this is for your job, I suggest:

如果这是为了你的工作，我建议：

1. do not reinvent the wheeland
2. use/buy COTSinstead of fiddling with bits.
3. Save your time/energy for solving business problems.

1. 不要重新发明轮子和
2. 使用/购买 COTS而不是摆弄位。
3. 节省您解决业务问题的时间/精力。

回答by SingleNegationElimination

What balanced means depends a bit on the structure at hand. For instance, A B-Tree cannot have nodes more than a certain depth from the root, or less for that matter, all data lives at a fixed depth from the root, but it can be out of balance if the distribution of leaves to leaves-but-one nodes is uneven. Skip-lists Have no notion at all of balance, relying instead on probability to achieve decent performance. Fibonacci trees purposefully fall out of balance, postponing the rebalance to achieve superior asymptotic performance in exchange for occasionally longer updates. AVL and Red-Black trees attach metadata to each node to attain a depth-balance invariant.

平衡意味着什么取决于手头的结构。例如，B-Tree 的节点不能超过距根的某个深度，或者更小，所有数据都位于距根的固定深度，但如果叶子到叶子的分布可能会失去平衡-but-one 节点是不均匀的。跳过列表完全没有平衡的概念，而是依靠概率来实现体面的性能。斐波那契树故意失去平衡，推迟重新平衡以实现卓越的渐近性能，以换取偶尔更长的更新。AVL 和红黑树将元数据附加到每个节点以获得深度平衡不变性。

All of these structures and more are present in the standard libraries of most common programming systems (except python, RAGE!). Implementing one or two is good programming practice, but its probably not a good use of time to roll your own for production, unless your problem has some peculiar performance need not satisfied by any off-the-shelf collections.

所有这些结构以及更多结构都存在于大多数常见编程系统的标准库中（python、RAGE 除外！）。实现一两个是很好的编程实践，但它可能不是一个很好的利用时间来生产自己的，除非你的问题有一些特殊的性能需要任何现成的集合不能满足。

回答by Sumit Kishore

Wouldn't this work?

这行不通？

return ( ( Math.abs( size( root.left ) - size( root.right ) ) < 2 );

Any unbalanced tree would always fail this.

任何不平衡的树都会​​失败。

回答by Eric Lippert

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.

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

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.

规范：如果（1）它是空的，或者（2）它的左右孩子高度平衡并且左树的高度在 1右树的高度。

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 massivelyunbalanced. 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 nearestempty child is within one of the path to the farthestempty child. My definition is less strict than that, and therefore admits more trees.

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

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.

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

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.

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

回答by Potatoswatter

Here is a version based on a generic depth-first traversal. Should be faster than the other correct answer and handle all the mentioned "challenges." Apologies for the style, I don't really know Java.

这是一个基于通用深度优先遍历的版本。应该比其他正确答案更快并处理所有提到的“挑战”。为风格道歉，我真的不知道Java。

You can still make it much faster by returning early if max and min are both set and have a difference >1.

如果 max 和 min 都已设置并且差异 >1，您仍然可以通过提前返回来使其更快。

public boolean isBalanced( Node root ) {
    int curDepth = 0, maxLeaf = 0, minLeaf = INT_MAX;
    if ( root == null ) return true;
    while ( root != null ) {
        if ( root.left == null || root.right == null ) {
            maxLeaf = max( maxLeaf, curDepth );
            minLeaf = min( minLeaf, curDepth );
        }
        if ( root.left != null ) {
            curDepth += 1;
            root = root.left;
        } else {
            Node last = root;
            while ( root != null
             && ( root.right == null || root.right == last ) ) {
                curDepth -= 1;
                last = root;
                root = root.parent;
            }
            if ( root != null ) {
                curDepth += 1;
                root = root.right;
            }
        }
    }
    return ( maxLeaf - minLeaf <= 1 );
}

回答by Brian

Bonus exercise response. The simple solution. Obviously in a real implementation one might wrap this or something to avoid requiring the user to include height in their response.

奖金锻炼反应。简单的解决方案。显然，在实际实现中，人们可能会包装这个或其他东西，以避免要求用户在他们的响应中包含高度。

IsHeightBalanced(tree, out height)
    if (tree is empty)
        height = 0
        return true
    balance = IsHeightBalanced(tree.left, heightleft) and IsHeightBalanced(tree.right, heightright)
    height = max(heightleft, heightright)+1
    return balance and abs(heightleft - heightright) <= 1