algorithm - 证明 AVL 树可以有节点数不是彼此的 Θ 的子节点

Question

_{令 T 为左子树为 T L}且右子树为 T _R的 AVL 树。让我们|T _L | 和 |T _R | 分别为左右子树的节点数。

我需要证明 |T _R | ≠ Θ(|T _R |) 反之亦然，但我不知道怎么做。我认为这与一棵树是完整的 AVL 树而另一棵树是最小的 AVL 树（斐波那契树）的情况有关，但我不知道从那里该怎么做。

Answer 1

在高度为 h 的 AVL 树中，节点的数量在 F _h+2 - 1 和 2 ^h - 1 之间。第一个数量是 Θ(φ ^h )，第二个是 Θ(2 ^h )，其中 φ 是黄金比率，大约为 1.61。这意味着您可以构建左子树中的节点数为 Θ(φ ^h ) 且右子树为 Θ(2 ^h ) 的 AVL 树，这意味着左子树的节点数渐近地少于右子树。然后您可以左右反转以显示右子树也不能是左子树的 Θ。

希望这可以帮助！