Definition of a Balanced Tree

I am just wondering if someone might be able to clarify the definition of a balanced tree for me. I have that "a tree is balanced if each sub-tree is balanced and the height of the two sub-trees differ by at most one.

I apologize if this is a dumb question, but does this definition apply to every node all the way down to the leaves of a tree or only to the left and right sub-trees immediately off the root? I guess another way to frame this would be, is it possible for internal nodes of a tree to be unbalanced and the whole tree to remain balanced?

135323 次浏览
小开

这两件事没有区别，想想看。

Let's take a simpler definition, "A positive number is even if it is zero or that number minus two is even." Does this say 8 is even if 6 is even? Or does this say 8 is even if 6, 4, 2, and 0 are even?

没有区别。如果它说8即使6是偶数，它也说6即使4是偶数。因此它也说4是偶数，如果2是偶数。因此它说2是偶数，如果0是偶数。所以如果它说8是偶数6是偶数，它(间接地)说8是偶数6,4,2,0是偶数。

这里也一样。任何间接子树都可以通过直接子树链找到。因此，即使它只直接应用于直接子树，它仍然间接应用于所有子树(因此所有节点)。

小开

约束通常递归地应用于每个子树，也就是说，只有在下列情况下，树才是平衡的:

  1. 左右子树的高度最多相差一个，AND
  2. 左边的子树是平衡的，AND
  3. 正确的子树是平衡的

根据这个，下一棵树是平衡的:

     A
/   \
B     C
/     / \
D     E   F
/
G

下一个是 没有平衡，因为 C 的子树高度相差2:

     A
/   \
B     C   <-- difference = 2
/     /
D     E
/
G

也就是说，第一个点的特定约束取决于树的类型。上面列出的是典型的 美国吸血鬼联盟的树。

例如，红黑树 施加了一个较软的约束。

小开

There are several ways to define "Balanced". The main goal is to keep the depths of all nodes to be O(log(n)).

It appears to me that the balance condition you were talking about is for AVL 树.
以下是 AVL tree's balance condition的正式定义:

对于 AVL 中的任何节点，其左侧子树的高度与其右侧子树的高度相差 最多1。

Next question, what is "height"?

二叉树中节点的“ 身高”是从该节点到叶子的最长路径的长度。

There is one weird but common case:

人们将空树的高度定义为 (-1)。

例如，root 的左边子节点是 null:

              A  (Height = 2)
/     \
(height =-1)       B (Height = 1) <-- Unbalanced because 1-(-1)=2 >1
\
C (Height = 0)

Two more examples to determine:

是的，一棵平衡的树例如:

        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)
小开

平衡树是一种高度为 log (树中元素的数量)的树。

height = O(log(n))
O, as in asymptotic notation i.e. height should have same or lower asymptotic
growth rate than log(n)
n: number of elements in the tree

给出了“每个子树的一棵树是平衡的，两个子树的高度相差不超过一棵”的定义，然后给出了 AVL 树。

因为 AVL 树是平衡的，但并不是所有的平衡树都是 AVL 树，平衡树没有这个定义，它们内部的节点可能是不平衡的。但是，AVL 树需要平衡所有内部节点。

小开

平衡树的目标是以最小的遍历(最小高度)到达叶子。 树的度是分支数减去1。 平衡树可能不是二进制树。

小开
  1. 树中节点的高度是从该节点向下到叶子的最长路径的长度，同时计算路径的起点和终点。
  2. 如果子树的高度相差不超过1，则树中的节点是高度平衡的。
  3. 如果树的所有节点都是高度平衡的，则该树是高度平衡的。
小开

查看左侧子树和右侧子树的递归定义可以等同于以下定义:

一个二叉树是平衡的当且仅当，对于每个节点 N，它的左边子树的高度和它的右边子树的高度最多相差1。

注意，这应该适用于所有节点。它们是等价的定义。后者可能更容易理解。你也可以认为它是一个“迭代定义”，与“递归定义”相比


提交答案