AVL树的树高上下界极清晰推导_avl数的高度推导

定义与设定

树上某点的高度是这个点到它子树上叶子节点所经过的最大边数，树的高度定义为根节点的高度。
以下的思路均是设树高为h，求树的最大(树高下界)和最小叶子数(树高上界)。

最小树高

当树高为h是，最大点数当然是把能填的都填满，成满二叉树。这样点数$$n=2^{h+1}-1$$导出h就是$$h=lo{g}_2(n+1)-1$$这个结果就是树高的下界。

最大树高

树高一定时，每个点的左右子树高低都差1时树的点数最少。高度为h是点数最小的话，左右子树高度分别是h-1和h-2，那总点数为$$\begin{gathered} n(h)=n(h-1)+n(h-2)+1， \\ n(0)=1,n(1)=2 \end{gathered}$$

通项公式

这个递推式通项公式比较经典。有多种方法。

矩阵法，简单粗暴

比如直接写成3*3矩阵连乘的形式，求出3个特征值把底数矩阵对角化了，直接就导出通项公式，非常暴力。

斐波那契法，方便巧妙

也可以变换以下得出这个递推和斐波那契数列的关系：
左右同时+1得到$$n(h)+1=(n(h-2)+1)+(n(h-1)+1)$$
看看首项的关系就会推出：$$n(h)=f(h+3)-1$$
斐波那契数列的通项公式求法更多了，其中最简单的是google一下抄过来，所以$$n(h)=\frac{1}{\sqrt{5}}\left[{\left(\frac{1+\sqrt{5}}{2}\right)}^{h+3}-{\left(\frac{1-\sqrt{5}}{2}\right)}^{h+3}\right]-1>\frac{1}{\sqrt{5}}{\left(\frac{1+\sqrt{5}}{2}\right)}^{h+3}-2$$这里用了放缩，不放缩的话h不好解出来，所以放缩了:$$\frac{1}{\sqrt{5}}{\left(\frac{1-\sqrt{5}}{2}\right)}^{h+3}<1$$
把h解出来：
$$h<[lo{g}_{\frac{1+\sqrt{5}}{2}}\sqrt{5}(n(h)+2)]-3$$
把对数形式用换底公式统一成以2为底的对数变成：
$$h<\frac{{\log }_2\left(n(h)+2\right)}{{\log }_2\left(\frac{1+\sqrt{5}}{2}\right)}+\frac{{\log }_2\sqrt{5}}{{\log }_2\left(\frac{1+\sqrt{5}}{2}\right)}-3$$
即
$$h<1.44042{\log }_2\left(n+2\right)-1.32772$$
这就是高度的上界。