从那些学年起已经有一段时间了。在一家医院找到了一份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;
}
这是一个好的实现吗？还是我错过了什么？
在寻找其他东西时偶然发现了这个老问题。我注意到你从来没有得到一个完整的答案。
解决此问题的方法是首先为您尝试编写的函数编写规范。
规范：如果（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)
将其翻译成您选择的编程语言应该是微不足道的。
额外练习：这个幼稚的代码草图在计算高度时遍历树的次数太多了。你能让它更有效率吗？
超级奖金练习：假设树是巨大的不平衡。例如，一侧有一百万个节点，另一侧有三个深度。是否存在此算法会破坏堆栈的情况？你能修复实现，使它永远不会破坏堆栈，即使给定一个严重不平衡的树？
更新：Donal Fellows在他的回答中指出，人们可以选择“平衡”的不同定义。例如，可以对“高度平衡”进行更严格的定义，并要求到最近的空子节点的路径长度在到最远的空子节点的路径之一内。我的定义没有那么严格，因此承认更多的树。
一个也可以比我的定义更不严格;可以说，平衡树是每个分支上空树的最大路径长度相差不超过两个，三个或其他常数的树。或者最大路径长度是最小路径长度的一小部分，如一半或四分之一。
这通常并不重要。任何树平衡算法的要点都是为了确保您不会陷入一边有一百万个节点而另一边有三个节点的情况下。Donal的定义在理论上是好的，但在实践中，提出一种满足这种严格程度的树平衡算法是一件痛苦的事情。性能节省通常不能证明实施成本是合理的。你花了很多时间做不必要的树重排，以达到一个平衡的水平，在实践中几乎没有什么区别。谁在乎有时需要四十个分支才能到达一棵百万节点不完全平衡的树中最远的叶子，而理论上它只需要二十个完全平衡的树呢？关键是它永远不会需要一百万。从最坏的一百万次下降到最坏的四十例通常就足够了;您不必一直走到最佳情况。
平衡是一种真正微妙的属性;你认为你知道它是什么，但它很容易出错。特别是，即使是埃里克·利珀特（Eric Lippert）的（好）答案也是不对的。那是因为身高的概念是不够的。您需要具有树的最小和最大高度的概念（其中最小高度是从根到叶子的最小步数，最大值是...好吧，你明白了）。鉴于此，我们可以将平衡定义为：
任何分支的最大高度不超过任何分支的最小高度的一个树。
（这实际上意味着分支本身是平衡的;您可以选择相同的分支作为最大值和最小值。
验证此属性所需要做的就是对当前深度进行简单的树遍历跟踪。第一次回溯时，这为您提供了基线深度。之后的每次回溯时，您都会将新深度与基线进行比较
在代码中：
class Tree {
Tree left, right;
static interface Observer {
public void before();
public void after();
public boolean end();
}
static boolean traverse(Tree t, Observer o) {
if (t == null) {
return o.end();
} else {
o.before();
try {
if (traverse(left, o))
return traverse(right, o);
return false;
} finally {
o.after();
}
}
}
boolean balanced() {
final Integer[] heights = new Integer[2];
return traverse(this, new Observer() {
int h;
public void before() { h++; }
public void after() { h--; }
public boolean end() {
if (heights[0] == null) {
heights[0] = h;
} else if (Math.abs(heights[0] - h) > 1) {
return false;
} else if (heights[0] != h) {
if (heights[1] == null) {
heights[1] = h;
} else if (heights[1] != h) {
return false;
}
}
return true;
}
});
}
}
我想你可以在不使用观察者模式的情况下做到这一点，但我发现以这种方式推理更容易。
[编辑]：为什么你不能只拿每边的高度。请考虑以下树：
/\
/ \
/ \
/ \_____
/\ / \_
/ \ / / \
/\ C /\ / \
/ \ / \ /\ /\
A B D E F G H J
好吧，有点乱，但根的每一边都是平衡的：深度为2，，，，是深度3，和，，，是深度4。左分支的高度为 2（请记住，当您遍历分支时，高度会减小），右分支的高度为 3。然而，整个树并不平衡，因为 和 之间的高度差为 2。您需要一个最小值规范（尽管实际算法可能不太复杂，因为应该只有两个允许的高度）。CABDEFGHJCF
