對于n個節點的AVL樹，其高度最低的時候肯定為葉子節點只在最后一層和倒數第二層的時候。即對于2k?1<n≦2k+1?12^k-1< n\leqq 2^{k+1}-12k?1<n≦2k+1?1的時候下界都為kkk。因此下界為h=┌log2(n+1)┐?1h=\ulcorner log_2(n+1)\urcorner-1h=┌log2?(n+1)┐?1
對于上界，我們可以將問題轉換為高度為hhh的樹最少有多少節點。
最少的節點情況下：
我們設高度為hhh的樹最少節點為S(h)S(h)S(h)，觀察不難發現
S(1)=1S(1)=1 S(1)=1
S(2)=2S(2)=2 S(2)=2
S(h)=S(h?1)+S(h?2)+1S(h)=S(h-1)+S(h-2)+1 S(h)=S(h?1)+S(h?2)+1
將遞推式變形得到：
S(h)+1=[S(h?1)+1]+[S(h?2)+1]S(h)+1=[S(h-1)+1]+[S(h-2)+1] S(h)+1=[S(h?1)+1]+[S(h?2)+1]
我們不妨令F(h)=S(h)+1F(h)=S(h)+1F(h)=S(h)+1，則上述遞推式變為
F(1)=2F(1)=2 F(1)=2
F(2)=3F(2)=3 F(2)=3
F(h)=F(h?1)+F(h?2)F(h)=F(h-1)+F(h-2) F(h)=F(h?1)+F(h?2)
由線性特征根法，特征方程為x2=x+1x^2=x+1x2=x+1，解方程得到x1=1?52,x2=1+52x_1=\frac{1-\sqrt{5}}{2},x_2=\frac{1+\sqrt{5}}{2}x1?=21?5??,x2?=21+5??
得到數列的通項為F(h)=Ax1n+Bx2nF(h)=Ax_1^n+Bx_2^nF(h)=Ax1n?+Bx2n?，帶入F(1),F(2)F(1),F(2)F(1),F(2)，得到遞推式為
F(h)=5?3510(1?52)h+5+3510(1+52)hF(h)=\frac{5-3\sqrt{5}}{10}(\frac{1-\sqrt{5}}{2})^h+\frac{5+3\sqrt{5}}{10}(\frac{1+\sqrt{5}}{2})^h F(h)=105?35??(21?5??)h+105+35??(21+5??)h
S(h)=5?3510(1?52)h+5+3510(1+52)h?1S(h)=\frac{5-3\sqrt{5}}{10}(\frac{1-\sqrt{5}}{2})^h+\frac{5+3\sqrt{5}}{10}(\frac{1+\sqrt{5}}{2})^h-1 S(h)=105?35??(21?5??)h+105+35??(21+5??)h?1
當hhh比較大的時候前一項約等于0，因此上界為
S(h)?5+3510(1+52)h?1S(h)\doteq\frac{5+3\sqrt{5}}{10}(\frac{1+\sqrt{5}}{2})^h-1 S(h)?105+35??(21+5??)h?1
h=1.44log2(n+1)?0.328h=1.44log_2(n+1)-0.328 h=1.44log2?(n+1)?0.328
