平衡树的定义 [英] 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?

推荐答案

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

The constraint is generally applied recursively to every subtree. That is, the tree is only balanced if:

1. 左右子树的高度最多相差一，AND
2. 左子树是平衡的，并且
3. 右子树是平衡的

据此，下一棵树是平衡的:

According to this, the next tree is balanced:

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

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

The next one is not balanced because the subtrees of C differ by 2 in their height:

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

也就是说，第一点的具体约束取决于树的类型.上面列出的是AVL树的典型.

That said, the specific constraint of the first point depends on the type of tree. The one listed above is the typical for AVL trees.

红黑树，例如，强加了更软的约束.

Red-black trees, for instance, impose a softer constraint.

这篇关于平衡树的定义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！