use*_*514 111 java algorithm binary-tree data-structures
这些学年已经有一段时间了.在医院找到了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;
}
这是一个很好的实现吗？还是我错过了什么？
Eri*_*ert 163
在搜索其他内容时偶然发现了这个老问题.我注意到你从来没有得到完整的答案.
解决此问题的方法是首先为您要编写的函数编写规范.
规格:如果(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的定义在理论上很好,但在实践中,树木平衡算法会遇到严格的严格程度.性能节省通常不能证明实施成本.你花了很多时间做不必要的树重新排列,以达到一定程度的平衡,在实践中几乎没有什么区别.谁在乎它是否需要四十个树枝才能到达一个百万节点不完美平衡的树中最远的叶子,理论上它在一个完美平衡的树中只需要二十个？关键是它不会花费一百万.从最坏情况下的一百万到最糟糕的情况下,通常都是足够好的; 你不必一直走到最佳的情况.
Don*_*ows 26
平衡是一个真正微妙的财产; 你认为你知道它是什么,但它很容易出错.特别是,甚至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
OK,有点乱,但根本的每一面是平衡的:C是深度2, ,A,,B 是深3,和,,,是深度4.左分支2(记得高度的高度减小为你穿越分支),右分支的高度为3.然而,整体的树是不是因为有介于两者之间的2高度差平衡和.您需要一个minimax规范(尽管实际算法可能不那么复杂,因为应该只有两个允许的高度).DEFGHJCF
Bri*_*ian 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
Jes*_*sak 21
这仅确定树的顶层是否平衡.也就是说,你可以有一棵树,最左边和最右边有两根长枝,中间没有任何东西,这将是真的.在返回true之前,您需要以递归方式检查root.left并root.right查看它们是否内部平衡.
Jia*_* Li 19
后期订单解决方案,仅遍历树一次.时间复杂度为O(n),空间为O(1),它比自上而下的解决方案更好.我给你一个java版本的实现.
public static <T> boolean isBalanced(TreeNode<T> root){
return checkBalance(root) != -1;
}
private static <T> int checkBalance(TreeNode<T> node){
if(node == null) return 0;
int left = checkBalance(node.getLeft());
if(left == -1) return -1;
int right = checkBalance(node.getRight());
if(right == -1) return -1;
if(Math.abs(left - right) > 1){
return -1;
}else{
return 1 + Math.max(left, right);
}
}
cod*_*ict 15
高度平衡二叉树的定义是:
二叉树,其中每个节点的两个子树的高度从不相差超过1.
因此,空二叉树总是高度平衡的.
如果出现以下情况,非空二叉树的高度平衡:
考虑树:
A
\
B
/ \
C D
如图所示,左子树A是高度平衡的(因为它是空的),它的右子树也是如此.但是由于左子树的0高度和右子树的高度是不满足条件3,树仍然不是高度平衡的2.
即使左右子树的高度相等,下面的树也不是高度平衡的.您现有的代码将返回true.
A
/ \
B C
/ \
D G
/ \
E H
所以def中的每个词都非常重要.
这将有效:
int height(treeNodePtr root) {
return (!root) ? 0: 1 + MAX(height(root->left),height(root->right));
}
bool isHeightBalanced(treeNodePtr root) {
return (root == NULL) ||
(isHeightBalanced(root->left) &&
isHeightBalanced(root->right) &&
abs(height(root->left) - height(root->right)) <=1);
}
小智 7
这实际上比实际上更复杂.
算法如下:
设B =最低级节点的深度
如果abs(AB)<= 1,那么树是平衡的
小智 7
如果二进制树是否平衡,则可以通过Level order遍历来检查:
private boolean isLeaf(TreeNode root) {
if (root.left == null && root.right == null)
return true;
return false;
}
private boolean isBalanced(TreeNode root) {
if (root == null)
return true;
Vector<TreeNode> queue = new Vector<TreeNode>();
int level = 1, minLevel = Integer.MAX_VALUE, maxLevel = Integer.MIN_VALUE;
queue.add(root);
while (!queue.isEmpty()) {
int elementCount = queue.size();
while (elementCount > 0) {
TreeNode node = queue.remove(0);
if (isLeaf(node)) {
if (minLevel > level)
minLevel = level;
if (maxLevel < level)
maxLevel = level;
} else {
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
elementCount--;
}
if (abs(maxLevel - minLevel) > 1) {
return false;
}
level++;
}
return true;
}
平衡的手段取决于手头的结构.例如,A B-Tree不能拥有超过根的某个深度的节点,或者更少的节点,所有数据都存在于距离根的固定深度,但如果叶子分布到叶子,它可能会失去平衡但是一个节点不均匀.跳过列表完全没有概念平衡,而是依靠概率来实现良好的性能.Fibonacci树故意失去平衡,推迟重新平衡以实现优越的渐近性能,以换取偶尔更长时间的更新.AVL和红黑树将元数据附加到每个节点以获得深度平衡不变量.
所有这些结构和更多都存在于大多数常见编程系统的标准库中(除了python,RAGE!).实现一两个是很好的编程实践,但它可能不是很好地利用时间来自己进行生产,除非你的问题有一些特殊的性能不需要任何现成的集合.
| 归档时间： |
|
| 查看次数： |
118997 次 |
| 最近记录： |