如何求一棵有n个节点的AVL树的最大高度？

Question

我的练习考试中有一个问题如下： 给定一个有 23 个节点的二叉搜索树，如果它也具有 AVL 属性，那么该二叉搜索树的最大高度是多少？

我首先想到的是 avl 树的高度 b 必须小于 1.45log2(n)。 因此，使用 n = 23 的公式，如果四舍五入的话，我会得到类似 6.5、7 的结果。 但这个问题的答案似乎是5。1.44log2(n)不是实际的最大高度吗？为什么答案会是5？

Answer 1

在 AVL 树中，平衡因子必须在 -1 到 1 之间。因此，通过尽可能最大化不平衡性，您可以得到这棵具有 20 个节点的树：

                                 ________*_________
                                /                  \
                          _____*____             ___*__
                         /          \           /      \
                     ___*__          *         *        *
                    /      \        / \       / \      /
                   *        *      *   *     *   *    *
                  / \      /      /         /   
                 *   *    *      *         *
                /
               *

现在再添加三个节点不足以增加高度。如果我们在这棵树上方添加一个根，我们没有足够的节点来填充该新根下方的右子树（并保持平衡要求）。因此，唯一有效的选择是将这三个节点添加到上述树的叶子下方的某个位置，并且我们不能使高度大于现有高度。

所以答案是 5。