avl-tree - 最小高度 AVL 树

Question

我只是在阅读这篇（http://condor.depaul.edu/ntomuro/courses/417/notes/lecture1.html）论文，它证明了 AVL 树中的最小节点数。但是，我不明白结果的含义，因为 O(log n) 根本不是指节点数。这怎么可能是证明？但是，我确实了解第一步以及如何简化迭代。但是在第四步之后，我无法理解他到底在做什么（尽管我可以模糊地想象）。谁能向我解释一下，最后几行证明了什么，以及他如何在第 1 部分末尾简化表达式？

谢谢

Answer 1

O(logn) 确实指的是节点。“n”代表节点数。您可以通过意识到每个后续级别上的节点数量增加一倍来直观地考虑它。因为它是 AVL 树，所以在将节点推送到下一层之前，上一层必须是满的。这将树的高度限制为 logn，因为每一层的节点数都加倍。换句话说，节点数可以写为nodes=2^height - 1。当你求解高度和圆时，你得到logn。