问题
这些学年已经有一段时间了。在医院找到了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 热门回答(158 赞)
在搜索其他内容时偶然发现了这个老问题。我注意到你从来没有得到完整的答案。
解决此问题的方法是首先为你要编写的函数编写规范。
规格：如果(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的定义在理论上很好，但在实践中，树木平衡算法会遇到严格的严格程度。性能节省通常不能证明实施成本。你花了很多时间做不必要的树重新排列，以达到一定程度的平衡，在实践中几乎没有什么区别。谁在乎它是否需要四十个分支才能到达百万节点不完美平衡树中最远的叶子，理论上它可以在完美平衡的树中只需要二十个？关键是它永远不会花费一百万。从最坏情况下的一百万到最糟糕的情况下，通常都是足够好的;你不必一直走到最佳的情况。
#2 热门回答(25 赞)
平衡是一个真正微妙的财产;你认为你知道它是什么，但它很容易出错。特别是，甚至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;
}
});
}
}
我想你可以在不使用Observer模式的情况下做到这一点，但我发现这种方式更容易理解。
[编辑]：为什么你不能只采取每一方的高度。考虑这棵树：
/\
/ \
/ \
/ \_____
/\ / \_
/ \ / / \
/\ C /\ / \
/ \ / \ /\ /\
A B D E F G H J
行，有点杂乱，但根的各侧是平衡的：Cis深度2,A,B,D,Eare深度3，andF,G,H,Jare深度4.左分支的高度为2(记住当你遍历分支时高度减小)，右分支的高度为3.然而整体树是不平衡的，因为在C和F之间存在2的高度差异。你需要一个minimax规范(尽管实际算法可能不那么复杂，因为应该只有两个允许的高度)。
#3 热门回答(22 赞)
奖金锻炼反应。简单的解决方案。显然，在实际的实现中，可以包装这个或类似的内容以避免要求用户在其响应中包含高度。
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