tree - 平衡树的定义

Question

我只是想知道是否有人能为我澄清平衡树的定义。我认为“如果每个子树都是平衡的并且两个子树的高度最多相差一棵树，那么这棵树就是平衡的。

如果这是一个愚蠢的问题，我很抱歉，但是这个定义是否适用于一直到树的叶子的每个节点，或者仅适用于紧邻根的左右子树？我想另一种框架方式是，树的内部节点是否可能不平衡，而整个树保持平衡？

Answer 1

约束通常递归地应用于每个子树。也就是说，只有满足以下条件，树才是平衡的:

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

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

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

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

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

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

Red-black trees例如，施加更软的约束。