php 免费企业网站,网站建设专员工作职责,平面设计职业学校,查排名的网站对于n个节点的AVL树#xff0c;其高度最低的时候肯定为叶子节点只在最后一层和倒数第二层的时候。即对于2k−1n≦2k1−12^k-1 n\leqq 2^{k1}-12k−1n≦2k1−1的时候下界都为kkk。因此下界为h┌log2(n1)┐−1h\ulcorner log_2(n1)\urcorner-1h┌log2(n1)┐−1
对…对于n个节点的AVL树其高度最低的时候肯定为叶子节点只在最后一层和倒数第二层的时候。即对于2k−1n≦2k1−12^k-1 n\leqq 2^{k1}-12k−1n≦2k1−1的时候下界都为kkk。因此下界为h┌log2(n1)┐−1h\ulcorner log_2(n1)\urcorner-1h┌log2(n1)┐−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)
由线性特征根法特征方程为x2x1x^2x1x2x1解方程得到x11−52,x2152x_1\frac{1-\sqrt{5}}{2},x_2\frac{1\sqrt{5}}{2}x121−5,x2215
得到数列的通项为F(h)Ax1nBx2nF(h)Ax_1^nBx_2^nF(h)Ax1nBx2n带入F(1),F(2)F(1),F(2)F(1),F(2)得到递推式为 F(h)5−3510(1−52)h53510(152)hF(h)\frac{5-3\sqrt{5}}{10}(\frac{1-\sqrt{5}}{2})^h\frac{53\sqrt{5}}{10}(\frac{1\sqrt{5}}{2})^h F(h)105−35(21−5)h10535(215)h
S(h)5−3510(1−52)h53510(152)h−1S(h)\frac{5-3\sqrt{5}}{10}(\frac{1-\sqrt{5}}{2})^h\frac{53\sqrt{5}}{10}(\frac{1\sqrt{5}}{2})^h-1 S(h)105−35(21−5)h10535(215)h−1
当hhh比较大的时候前一项约等于0因此上界为 S(h)≐53510(152)h−1S(h)\doteq\frac{53\sqrt{5}}{10}(\frac{1\sqrt{5}}{2})^h-1 S(h)≐10535(215)h−1
h1.44log2(n1)−0.328h1.44log_2(n1)-0.328 h1.44log2(n1)−0.328
