平衡树的定义
我只是想知道是否有人能够为我澄清一个平衡树的定义。 我有这样的说法：“每棵子树的树是平衡的，两棵子树的高度最多相差一个。
我很抱歉，如果这是一个愚蠢的问题，但是这个定义是否适用于每一个节点一直到树的叶子，或只有左侧和右侧的子树，我想另一种方式来问这个是问一个树的内部节点是否可能不平衡，整棵树保持平衡？
约束通常recursion地应用于每个子树。 也就是说，只有在以下情况下树才是平衡的：
- 左右子树的高度相差至多一个，AND
- 左子树是平衡的，AND
- 正确的子树是平衡的
据此，下一棵树是平衡的：
A / \ BC / / \ DEF / G 下一个是不平衡的，因为C的子树的高度相差2。
A / \ BC <-- difference = 2 / / DE / G
也就是说，第一点的具体约束取决于树的types。 上面列出的是AVL树的典型。
例如， 红黑树限制较轻。
有几种方法来定义“平衡”。 主要目标是保持所有节点的深度为O(log(n)) 。
在我看来，你所说的平衡条件是AVL树 。
这里是AVL树的平衡条件的正式定义：
对于AVL中的任何节点，其左侧子树的高度与其右侧子树的高度相差至多 1。
下一个问题，什么是“ 身高 ”？
二叉树中节点的“ 高度 ”是从该节点到树叶的最长path的长度。
有一个奇怪但常见的情况：
人们将空树的高度定义为
(-1)。
例如，root的左边的孩子是null ：
A (Height = 2) / \ (height =-1) B (Height = 1) <-- Unbalanced because 1-(-1)=2 >1 \ C (Height = 0)
还有两个例子可以确定：
是的， 平衡树例子：
A (h=3) / \ B(h=1) C (h=2) / / \ D (h=0) E(h=0) F (h=1) / G (h=0)
不， 不是一个平衡的树例如：
A (h=3) / \ B(h=0) C (h=2) <-- Unbalanced: 2-0 =2 > 1 / \ E(h=1) F (h=0) / \ H (h=0) G (h=0)
这两件事没有什么区别。 想想看。
我们来简单的定义一下，“正数即使为零，或者数字减2也是偶数”。 这是说8就算是6甚至？ 或者这是说8即使是6,4,2和0是偶数？
没有区别。 如果说8即使6是偶数，也就是说6即使4是偶数。 所以也就是说4就是2即使。 因此它说2即使是0也是。 所以如果说8即使6是偶数，也间接地说8即使是6,4,2和0是偶数。
这里是一样的东西。 任何间接子树都可以通过一系列直接的子树来find。 所以即使它只直接应用于直接子树，它仍然间接地应用于所有的子树（并且因此也是所有的节点）。
平衡树是高度为log的顺序（树中的元素的数量）的树。
height = O(log(n)) O, as in asymptotic notation ie height should have same or lower asymptotic growth rate than log(n) n: number of elements in the tree
定义“一棵树是平衡的，每棵子树是平衡的，两棵子树的高度相差最多一个”，其次是AVL树。
由于AVL树是平衡的，但并非所有的平衡树都是AVL树，所以平衡树不具有这个定义，内部节点可能不平衡。 但是，AVL树要求所有内部节点均衡。
平衡树的目标是以最小遍历（最小高度）达到叶子。 树的程度是分支数减1.平衡树可能不是二元的。
