algorithm - AVL树分析

Question

我正在阅读 Weiss 的数据结构和分析中的 AVL tres

平衡条件之一将坚持每个节点必须具有相同高度的左右子树。如果一个空子树的高度被定义为 -1（像往常一样），那么只有 ((2 到 k 次方) - 1) 个节点的完美平衡树才能满足这个标准。因此，尽管这保证了深度较小的树，但平衡条件过于僵化而无用，需要放松。

通过给出示例 1 请求帮助理解上述文本。比如作者如何使用 ((2 的 k 次幂) - 1) 节点满足此标准？2.“虽然这保证了树的深度较小，但平衡条件太僵硬而无用，需要放松”是什么意思？

谢谢！

Answer 1

如此处所述，完美平衡的树在任何节点的任一侧都具有相同数量的节点。可以满足这一点的树的总节点数为：

1: *

3: *
  / \
 *   *

7:  *
   / \
  *   *
 / \ / \
 * * * *

ETC

在数学上，这意味着树中的节点数是 2 ^k -1，其中k是一个整数。

“小深度”意味着这种形式的树在其给定深度下具有尽可能多的节点：再增加一个节点必须增加深度。