1. 高度下界

2. 高度上界

2.1. 最大高度对应 Node 数量 \(N_{h}\) 的递归公式

设有一棵 AVL tree 的高度为 \(h\), 对于该树, 其 node 数量为 \(N_{h}\).
有: 最坏情况下, root 的两棵 subtree 高度为 \(h-1\) 和 \(h-2\).
因此得到以下公式 (其中 \(h \in N^{+}\)):

\[N_{h}= \begin{cases} 0 &h=0 \\ 1 &h=1 \\ N_{h-1}+N_{h-2}+1 &h\geq2 \end{cases} \]

2.2. 数学归纳法证明 \(N_{h}=Fibonacci_{(h+2)}-1\)

已知:

\[\begin{aligned} N_{h}&=\begin{cases}0 &h=0 \\1 &h=1 \\N_{h-1}+N_{h-2}+1 &h\geq2\end{cases}\\ ~\\ F_{h}&=F_{h-1}+F_{h-2}~~h\geq2 \end{aligned} \]

且有:

\[N_{0}=F_{2}-1\\ N_{1}=F_{3}-1 \]

假设:

\[N_{k}=F_{k+2}-1,~k \in N^{+}~且~k\geq3 \]

则:

\[\begin{aligned} N_{k+3}&=N_{k+1}+N_{k+2}+1\\ &=F_{k+3}-1+F_{k+4}-1+1\\ &=F_{k+5}-1 \end{aligned} \]

假设成立.

2.3. \(N_{h}\) 的通项公式

已知 Fibonacci sequence 的通项公式为:

\[F_{n}=\frac{1}{\sqrt{5}}\bigg[\bigg(\frac{\sqrt{5}+1}{2}\bigg)^n + \bigg(\frac{\sqrt{5}-1}{2}\bigg)^n\bigg] \]

根据 2.2 的证明, 得到:

\[n=\frac{1}{\sqrt{5}}\bigg[\bigg(\frac{\sqrt{5}+1}{2}\bigg)^{h+2} + \bigg(\frac{\sqrt{5}-1}{2}\bigg)^{h+2}\bigg]-1 \]

即:

\[\frac{1}{\sqrt{5}}\bigg(\frac{\sqrt{5}+1}{2}\bigg)^{h+2} = n+1- \frac{1}{\sqrt{5}}\bigg(\frac{\sqrt{5}-1}{2}\bigg)^{h+2} \]

由于 \(t = \frac{1}{\sqrt{5}}\bigg(\frac{\sqrt{5}-1}{2}\bigg)^{h+2} \in (0,0.2)\), 为了更方便地求得 \(h\) 的上界, 这里假设 \(t=0\).
因此:

\[\begin{aligned} h&=\lfloor\log_{(\sqrt{5}+1) / 2}{\sqrt{5}(1-n)}-2\rfloor \\ &=O(\log{n}) \end{aligned} \]