时间戳

首页 > 解决方案 > 找到 AVL 树的最小“内部”节点？

data-structures - 找到 AVL 树的最小“内部”节点？

问题描述

我知道如何使用公式 n(h) = n(h-1) + n(h-2) + 1 找到高度为 h 的 AVL 树（包括外部节点）中的最小节点数，但我想知道如果有一个公式可以仅找到高度为 h 的 AVL 树的最小内部节点。

所以对于 n(3) = 4，如果我们只计算内部节点。n(4) = 7，如果我们只计算内部节点。我可以把它画出来并计算内部节点，但是当你得到更大的 AVL 树时，它就会变得一团糟。

我似乎在这方面找不到任何东西，试图找到一个答案一致的模式只会导致数小时的挫败感。提前致谢。

标签： data-structuresbinary-treeavl-tree

解决方案

是的，有一个很好的方法来计算这个。让我们从两个最简单的 AVL 树开始，它们的阶数为 0 和阶数为 1：

*    *
     |
     *

第一棵树没有内部节点，第二棵树有一个内部节点。这为我们提供了递归关系的基本情况：

  • 我（0）= 0
  • 我(1) = 1

从这里，我们注意到在 n+2 阶的 AVL 树中获得最少内部节点的方法是选择 n 和 n+1 阶的两棵树作为具有最少内部节点的子树（最小化节点数）可能的。结果树的内部节点数等于两个子树中的内部节点数，再加上一个新根。这意味着

  • I(n+2) = I(n) + I(n+1) + 1。

应用这个递归给了我们序列

0、1、2、4、7、12、20 等

嘿 - 我们以前在什么地方见过这个吗？我们有！在每个术语中添加一个给我们

1、2、3、5、8、13、21等

这是斐波那契数列，向下移动了两个位置！所以我们的假设是

I(n) = F(n+2) - 1

你可以通过对 n 的归纳来证明这一点。

这是获得此结果的另一种方法。想象一下，您采用高度为 n 的 AVL 树并删除所有叶子。您现在留下了高度为 n-1 的 AVL 树（证明这一点！），并且该树中的所有剩余节点都是原始树的内部节点。高度为 n 的 AVL 树中可能的最小节点数是 F(n+2)-1，与我们的结果相匹配。

推荐阅读