如何确定二叉树是否平衡？
这些学年已经有一段时间了。 在医院find了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）它的左右子节点是高度平衡的，并且左树的高度在正确的树的高度。
现在你已经有了这个规范，代码很简单。 只要按照规范：
IsHeightBalanced(tree) return (tree is empty) or (IsHeightBalanced(tree.left) and IsHeightBalanced(tree.right) and abs(Height(tree.left) - Height(tree.right)) <= 1)
把它翻译成你select的编程语言应该是微不足道的。
奖励练习：这个朴素的代码草图在计算高度时会经过很多次。 你能使它更有效率吗？
超级红利练习：假设树大量失衡。 就像一百万个节点深一点，另一个深三个。 有没有这种algorithm吹堆的情况？ 你能否修复这个实现，以至于即使在给定一个大量不平衡的树的时候，它也不会打碎堆栈？
更新：Donal Fellows在他的回答中指出，人们可以select不同的“均衡”定义。 例如，可以对“身高平衡”采取更严格的定义，并要求最近的空儿童的path长度在最远的空儿童的path之内。 我的定义不那么严格，因此承认更多的树木。
人们也可以不像我的定义那么严格。 人们可以说平衡树是一个平衡树，其中每个分支上的空树的最大path长度相差不超过两个或三个或其他常数。 或者说，最大path长度是最小path长度的一部分，如一半或四分之一。
这通常并不重要。 任何树平衡algorithm的要点是要确保你不会在一方有三百万个节点的情况下结束。 Donal的定义在理论上是好的，但是在实践中，遇到一个满足严格级别的树平衡algorithm是一个痛苦。 性能节省通常不能certificate实施成本。 你花了很多时间做不必要的树重新排列，以达到平衡的水平，实际上没有什么区别。 谁在乎有时需要四十个分支才能到达百万节点不完全平衡的树中的最远的叶子，理论上在一棵完全平衡的树上只需要二十棵呢？ 关键是它不会花费一百万。 从最坏的情况下，从一百万下降到最坏的情况下，通常是足够好的; 你不必一直走到最佳的情况。
平衡是一个真正微妙的财产; 你以为你知道这是什么，但是很容易出错。 特别是，即使Eric Lippert的（好）答案也没有。 那是因为高度的概念是不够的。 你需要有一个树的最小和最大高度的概念（其中最小高度是从根到叶的最less步数，最大值是…呃，你得到的图片）。 鉴于此，我们可以将平衡定义为：
任何分支的最大高度不超过任何分支的最小高度的树。
（这实际上意味着分支本身是平衡的;你可以select最大和最小分支。
所有你需要做的事情来validation这个属性是一个简单的树遍历跟踪当前的深度。 你第一次回溯，给你一个基线深度。 每次在回溯之后，您都会将新的深度与基线进行比较
- 如果它等于基线，那么你就继续
- 如果它不止一个，树就不平衡了
- 如果它是一次性的，那么你现在知道平衡的范围，并且所有随后的深度（当你要返回时）必须是第一或第二个值。
在代码中：
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 /\ / \ / \ / \ /\ /\ ABDEFGHJ
OK，有点乱，但是根的每一边是平衡的： C是深度2， A ， B ， D ， E是深度3， F ， G ， H ， J是深度4。 2（记住高度随着分支的移动而减小），右分支的高度是3.然而，总体树不平衡，因为C和F之间的高度差为2。 你需要一个最小规格（尽pipe实际algorithm可能不那么复杂，因为应该只有两个允许的高度）。
这只确定树的顶层是否平衡。 也就是说，你可以在最左边和最右边有一棵有两条长枝的树，中间没有任何东西，这将会返回true。 您需要recursion检查root.left和root.right以确定它们是否在内部平衡以及返回true之前。
奖金锻炼回应。 简单的解决scheme。 很显然，在一个真正的实现中，可以包装这个或者某个东西来避免要求用户在响应中包含高度。
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
发布订单解决scheme，只遍历树一次。 时间复杂度为O（n），空间为O（1），优于自顶向下的解决scheme。 我给你一个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); } }
高度平衡二叉树的定义是：
二叉树，其中每个节点的两个子树的高度相差不超过1。
所以，一个空的二叉树总是高度平衡的。
一个非空的二叉树是高度平衡的，如果：
- 它的左子树是高度平衡的。
- 它的右子树是高度平衡的。
- 左右子树的高度差不大于1。
考虑树：
A \ B / \ CD
如所看到的， A的左子树是高度平衡的（因为它是空的），其右子树也是如此。 但是由于左子树的高度为0 ，右子树的高度为2 ，条件3不满足，树仍然不是高度平衡的。
即使左右子树的高度相等，下面的树也不是高度平衡的。 您现有的代码将返回true。
A / \ BC / \ DG / \ EH
所以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); }
Ideone Link
这比现实要复杂得多。
algorithm如下：
- 设A =最高级别节点的深度
-
设B =最低级节点的深度
-
如果abs（AB）<= 1，那么树是平衡的
平衡的手段取决于手头的结构。 例如，一棵B树不能有超过一定深度的根节点，或者更less的情况下，所有的数据都是从根开始的一个固定的深度，但是如果叶子到树叶的分布可能是不平衡的但是一个节点是不平衡的。 跳过列表完全没有概念的平衡，而是依靠概率来实现体面的performance。 斐波那契树有意失去平衡，推迟重新平衡以获得更好的渐进性能，以换取偶尔更长的更新。 AVL和红黑树将元数据附加到每个节点以获得深度平衡不variables。
所有这些结构和更多的是在大多数常见的编程系统的标准库（python，RAGE！除外）中。 实现一个或两个是很好的编程实践，但它可能不是一个很好的使用时间来滚动你自己的生产，除非你的问题有一些特殊的性能需要任何现成的collections不满足。
注1：任何子树的高度只计算一次。
注2：如果左子树不平衡，则可能包含百万个元素的右子树的计算被跳过。
// return height of tree rooted at "tn" if, and only if, it is a balanced subtree // else return -1 int maxHeight( TreeNode const * tn ) { if( tn ) { int const lh = maxHeight( tn->left ); if( lh == -1 ) return -1; int const rh = maxHeight( tn->right ); if( rh == -1 ) return -1; if( abs( lh - rh ) > 1 ) return -1; return 1 + max( lh, rh ); } return 0; } bool isBalanced( TreeNode const * root ) { // Unless the maxHeight is -1, the subtree under "root" is balanced return maxHeight( root ) != -1; }
平衡通常取决于每个方向上最长path的长度。 上面的algorithm不会为你做。
你想要实现什么？ 有自我平衡的树木（AVL /红黑色）。 实际上，Java树是平衡的。
如果这是你的工作 ，我build议：
- 不要重新发明轮子
- 使用/购买COTS而不是摆弄位。
- 节省您的时间/精力来解决业务问题。
public boolean isBalanced(TreeNode root) { return (maxDepth(root) - minDepth(root) <= 1); } public int maxDepth(TreeNode root) { if (root == null) return 0; return 1 + max(maxDepth(root.left), maxDepth(root.right)); } public int minDepth (TreeNode root) { if (root == null) return 0; return 1 + min(minDepth(root.left), minDepth(root.right)); }
#include <iostream> #include <deque> #include <queue> struct node { int data; node *left; node *right; }; bool isBalanced(node *root) { if ( !root) { return true; } std::queue<node *> q1; std::queue<int> q2; int level = 0, last_level = -1, node_count = 0; q1.push(root); q2.push(level); while ( !q1.empty() ) { node *current = q1.front(); level = q2.front(); q1.pop(); q2.pop(); if ( level ) { ++node_count; } if ( current->left ) { q1.push(current->left); q2.push(level + 1); } if ( current->right ) { q1.push(current->right); q2.push(level + 1); } if ( level != last_level ) { std::cout << "Check: " << (node_count ? node_count - 1 : 1) << ", Level: " << level << ", Old level: " << last_level << std::endl; if ( level && (node_count - 1) != (1 << (level-1)) ) { return false; } last_level = q2.front(); if ( level ) node_count = 1; } } return true; } int main() { node tree[15]; tree[0].left = &tree[1]; tree[0].right = &tree[2]; tree[1].left = &tree[3]; tree[1].right = &tree[4]; tree[2].left = &tree[5]; tree[2].right = &tree[6]; tree[3].left = &tree[7]; tree[3].right = &tree[8]; tree[4].left = &tree[9]; // NULL; tree[4].right = &tree[10]; // NULL; tree[5].left = &tree[11]; // NULL; tree[5].right = &tree[12]; // NULL; tree[6].left = &tree[13]; tree[6].right = &tree[14]; tree[7].left = &tree[11]; tree[7].right = &tree[12]; tree[8].left = NULL; tree[8].right = &tree[10]; tree[9].left = NULL; tree[9].right = &tree[10]; tree[10].left = NULL; tree[10].right= NULL; tree[11].left = NULL; tree[11].right= NULL; tree[12].left = NULL; tree[12].right= NULL; tree[13].left = NULL; tree[13].right= NULL; tree[14].left = NULL; tree[14].right= NULL; std::cout << "Result: " << isBalanced(tree) << std::endl; return 0; }
如果二叉树是平衡的，可以通过级别遍历来检查：
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; }
这里是一个完整的C＃testing解决scheme（对不起，我不是Java开发）（只需复制控制台应用程序粘贴）。 我知道平衡的定义并不是每个人都可能喜欢我的testing结果，但是请看看在recursion循环中检查深度/高度和在第一次不匹配时退出而不保存每个节点上的节点高度/级别/深度（只保留它在一个函数调用）。
using System; using System.Linq; using System.Text; namespace BalancedTree { class Program { public static void Main() { //Value Gathering Console.WriteLine(RunTreeTests(new[] { 0 })); Console.WriteLine(RunTreeTests(new int[] { })); Console.WriteLine(RunTreeTests(new[] { 0, 1, 2, 3, 4, -1, -4, -3, -2 })); Console.WriteLine(RunTreeTests(null)); Console.WriteLine(RunTreeTests(new[] { 10, 8, 12, 8, 4, 14, 8, 10 })); Console.WriteLine(RunTreeTests(new int[] { 20, 10, 30, 5, 15, 25, 35, 3, 8, 12, 17, 22, 27, 32, 37 })); Console.ReadKey(); } static string RunTreeTests(int[] scores) { if (scores == null || scores.Count() == 0) { return null; } var tree = new BinarySearchTree(); foreach (var score in scores) { tree.InsertScore(score); } Console.WriteLine(tree.IsBalanced()); var sb = tree.GetBreadthWardsTraversedNodes(); return sb.ToString(0, sb.Length - 1); } } public class Node { public int Value { get; set; } public int Count { get; set; } public Node RightChild { get; set; } public Node LeftChild { get; set; } public Node(int value) { Value = value; Count = 1; } public override string ToString() { return Value + ":" + Count; } public bool IsLeafNode() { return LeftChild == null && RightChild == null; } public void AddValue(int value) { if (value == Value) { Count++; } else { if (value > Value) { if (RightChild == null) { RightChild = new Node(value); } else { RightChild.AddValue(value); } } else { if (LeftChild == null) { LeftChild = new Node(value); } else { LeftChild.AddValue(value); } } } } } public class BinarySearchTree { public Node Root { get; set; } public void InsertScore(int score) { if (Root == null) { Root = new Node(score); } else { Root.AddValue(score); } } private static int _heightCheck; public bool IsBalanced() { _heightCheck = 0; var height = 0; if (Root == null) return true; var result = CheckHeight(Root, ref height); height--; return (result && height == 0); } private static bool CheckHeight(Node node, ref int height) { height++; if (node.LeftChild == null) { if (node.RightChild != null) return false; if (_heightCheck != 0) return _heightCheck == height; _heightCheck = height; return true; } if (node.RightChild == null) { return false; } var leftCheck = CheckHeight(node.LeftChild, ref height); if (!leftCheck) return false; height--; var rightCheck = CheckHeight(node.RightChild, ref height); if (!rightCheck) return false; height--; return true; } public StringBuilder GetBreadthWardsTraversedNodes() { if (Root == null) return null; var traversQueue = new StringBuilder(); traversQueue.Append(Root + ","); if (Root.IsLeafNode()) return traversQueue; TraversBreadthWards(traversQueue, Root); return traversQueue; } private static void TraversBreadthWards(StringBuilder sb, Node node) { if (node == null) return; sb.Append(node.LeftChild + ","); sb.Append(node.RightChild + ","); if (node.LeftChild != null && !node.LeftChild.IsLeafNode()) { TraversBreadthWards(sb, node.LeftChild); } if (node.RightChild != null && !node.RightChild.IsLeafNode()) { TraversBreadthWards(sb, node.RightChild); } } } }
那么，你需要一种方法来确定左右的高度，如果左右平衡的话。
我只是return height(node->left) == height(node->right);
至于写height函数，请阅读： 了解recursion
你在说什么树？ 那里有自我平衡的树木。 检查他们的algorithm，他们确定他们是否需要重新sorting树，以保持平衡。
这是一个基于通用深度优先遍历的版本。 应该比其他正确的答案更快，并处理所有提到的“挑战”。 对这种风格抱歉，我不太了解Java。
如果最大值和最小值都被设置，并且差异> 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 ); }
boolean isBalanced(Node root) { if (longestPath(root) - shortestPath(root) > 1) return false; else return true; } int longestPath(Node root) { if (root == null); return 0; else { int leftPathLength = longestPath(root.left); int rightPathLength = longestPath(root.right); if (leftPathLength >= rightPathLength) return leftPathLength + 1; else return rightPathLength + 1; } } int shortestPath(Node root) { if (root == null); return 0; else { int leftPathLength = shortestPath(root.left); int rightPathLength = shortestPath(root.right); if (leftPathLength <= rightPathLength) return leftPathLength + 1; else return rightPathLength + 1; } }
这是我为埃里克的奖金练习所尝试的。 我试图放松我的recursion循环，只要我发现一个子树不平衡，就返回。
int heightBalanced(node *root){ int i = 1; heightBalancedRecursive(root, &i); return i; } int heightBalancedRecursive(node *root, int *i){ int lb = 0, rb = 0; if(!root || ! *i) // if node is null or a subtree is not height balanced return 0; lb = heightBalancedRecursive(root -> left,i); if (!*i) // subtree is not balanced. Skip traversing the tree anymore return 0; rb = heightBalancedRecursive(root -> right,i) if (abs(lb - rb) > 1) // not balanced. Make i zero. *i = 0; return ( lb > rb ? lb +1 : rb + 1); // return the current height of the subtree }
public int height(Node node){ if(node==null)return 0; else{ int l=height(node.leftChild); int r=height(node.rightChild); return(l>r?l+1:r+1); }} public boolean balanced(Node n){ int l= height(n.leftChild); int r= height(n.rightChild); System.out.println(l + " " +r); if(Math.abs(lr)>1) return false; else return true; }
一棵空树是高度平衡的。 一个非空的二叉树T是平衡的，如果：
1）T的左子树是平衡的
2）T的右子树是平衡的
3）左子树和右子树高度之差不大于1。
/* program to check if a tree is height-balanced or not */ #include<stdio.h> #include<stdlib.h> #define bool int /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; }; /* The function returns true if root is balanced else false The second parameter is to store the height of tree. Initially, we need to pass a pointer to a location with value as 0. We can also write a wrapper over this function */ bool isBalanced(struct node *root, int* height) { /* lh --> Height of left subtree rh --> Height of right subtree */ int lh = 0, rh = 0; /* l will be true if left subtree is balanced and r will be true if right subtree is balanced */ int l = 0, r = 0; if(root == NULL) { *height = 0; return 1; } /* Get the heights of left and right subtrees in lh and rh And store the returned values in l and r */ l = isBalanced(root->left, &lh); r = isBalanced(root->right,&rh); /* Height of current node is max of heights of left and right subtrees plus 1*/ *height = (lh > rh? lh: rh) + 1; /* If difference between heights of left and right subtrees is more than 2 then this node is not balanced so return 0 */ if((lh - rh >= 2) || (rh - lh >= 2)) return 0; /* If this node is balanced and left and right subtrees are balanced then return true */ else return l&&r; } /* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */ /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode(int data) { struct node* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return(node); } int main() { int height = 0; /* Constructed binary tree is 1 / \ 2 3 / \ / 4 5 6 / 7 */ struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->left->left->left = newNode(7); if(isBalanced(root, &height)) printf("Tree is balanced"); else printf("Tree is not balanced"); getchar(); return 0; }
时间复杂度：O（n）
为了在巨大的树木上有更好的performance，你可以节省每个节点的高度，这样就是一个折衷的空间Vs性能：
class Node { Node left; Node right; int value; int height; }
实施添加和删除相同的示例
void addNode(Node root,int v) { int height =0; while(root != null) { // Since we are adding new node so the height // will increase by one in each node we will pass by root.height += 1; height++; else if(v > root.value){ root = root.left(); } else{ root = root.right(); } } height++; Node n = new Node(v , height); root = n; } int treeMaxHeight(Node root) { return Math.Max(root.left.height,root.right.height); } int treeMinHeight(Node root) { return Math.Min(root.left.height,root.right.height); } Boolean isNodeBlanced(Node root) { if (treeMaxHeight(root) - treeMinHeight(root) > 2) return false; return true; } Boolean isTreeBlanced (Node root) { if(root == null || isTreeBalanced(root.left) && isTreeBalanced(root.right) && isNodeBlanced(root)) return true; return false; }
static boolean isBalanced(Node root) { //check in the depth of left and right subtree int diff = depth(root.getLeft()) - depth(root.getRight()); if (diff < 0) { diff = diff * -1; } if (diff > 1) { return false; } //go to child nodes else { if (root.getLeft() == null && root.getRight() == null) { return true; } else if (root.getLeft() == null) { if (depth(root.getRight()) > 1) { return false; } else { return true; } } else if (root.getRight() == null) { if (depth(root.getLeft()) > 1) { return false; } else { return true; } } else if (root.getLeft() != null && root.getRight() != null && isBalanced(root.getLeft()) && isBalanced(root.getRight())) { return true; } else { return false; } } }
这不会工作吗？
return ( ( Math.abs( size( root.left ) - size( root.right ) ) < 2 );
任何不平衡的树总是会失败。
