1

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

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

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

谢谢!

4

1 回答 1

1

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

1: *

3: *
  / \
 *   *

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

ETC

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

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

于 2011-08-31T11:52:08.830 回答