高度为 h 的 AVL 树中的最小节点数是多少？我在互联网上做了一些研究，但它们都很混乱。
问问题
16952 次
3 回答
9
n(h)为高度为 h 的 AVL 树的最小节点数，则：
n(0)=1, n(1)=2
n(h)= 1+n(h-1)+n(h-2)
于 2013-07-15T15:29:48.863 回答
4
对于高度为 h 的树，AVL 树中的最小节点数。以下等式应演示 N(h) 函数的递归调用。
formula N(h)=1+N(h-1)+N(h-2)
由于我们知道N(0)=1 ,N(1) = 2, N(2) = 4，例如：我们可以将以下等式简化为 的这些已知值h = 6。
N(3)=1+N(3-1)+N(3-2)=1+N(2)+N(1)=7
N(4)=1+N(4-1)+N(4-2)=1+N(3)+N(2)=12
N(5)=1+N(5-1)+N(5-2)=1+N(4)+N(3)=20
N(6)=1+N(6-1)+N(6-2)=1+N(5)+N(4)=33
于 2016-01-13T15:55:09.993 回答
0
高度为 h 的 AVL 树至少有 2(h/2)-1 个内部节点。
证明：设 n(h) 为高度为 h 的 AVL 树中的最小内部节点数。
n(1)=1 且 n(2)=2。所以引理适用于 h=1 和 h=2。
于 2012-10-20T04:25:12.447 回答