AVL树最小节点

Question

AVL树在高度为h时的最小节点数是多少？我在网上做了一些研究，但它们都很混乱。

- Chin

Answer 1

假设 n(h) 是一个高度为 h 的 AVL 树的最小节点数，则有：

n(0)=1, n(1)=2
n(h)= 1+n(h-1)+n(h-2)

- beNick

Answer 2

AVL树高度为h时，最小节点数为N(h)。以下公式展示了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

- Rana Priyanka

Answer 3

一棵高度为h的AVL树至少有2(h/2)-1个内部节点。

证明：设n(h)为高度为h的AVL树中最小的内部节点数。

n(1)=1且n(2)=2。因此引理对于h=1和h=2成立。

- NullPoiиteя

---

这里不存在存在证明。 - technical_difficulty