问答题
一棵具有m层的AVL树至少有多少个结点，最多有多少个结点? 【浙江大学1995六(8分)】
【正确答案】正确答案：设以N
m
表示深度为m的AVL树中含有的最少结点数。显然，N
0
=0，N
1
=1，N
2
=2，且N
m
=N
m-1
+N
m-2
+1(m≥2)。这个关系与斐波那契序列类似，用归纳法可以证明：当m≥0时，N
m
=F
m+2
—1，而F
m
约等于
(其中
)，则N
m
约等于
(其中
)，则N
m
约等于
【答案解析】