文章/答案/技术大牛

发布

社区首页 >问答首页 >给定高度的AVL树的最大高度是多少？

问给定高度的AVL树的最大高度是多少？
EN

Stack Overflow用户

提问于 2019-02-25 12:00:57

回答 2查看 967关注 0票数 2

我在寻找一个递归公式来寻找高度为h的最大高度AVL树的数量时遇到了一些麻烦。高度0有1，高度1有2，高度2有4，高度3有8，等等，对吗？

回答已采纳

发布于 2019-02-25 19:15:06

让我们从另一个角度来看这个问题。

让我们找出给定高度的最小节点数，而不是给定节点数的最大高度。对于这个问题，我们有一个递归函数：n(h) = n(h-1) + n(h-2) + 1，因为您需要在右子树中至少有n(h-1)节点，在左子树中至少需要n(h-2)节点，并且需要一个节点作为根。

(图片和更完整的解释here)。

考虑到这一点，您必须找到一个满足n(h) < n < n(h+1)的h，其中n是您给定的节点数。

顺便说一句，简短的答案是h < 2log(n) + 2

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/54859328

复制

相似问题

问给定高度的AVL树的最大高度是多少？EN