- 1使用OpenLayers库展示高德瓦片地图
- 2面试计算机有什么优势和不足,面试时如何介绍自己的优缺点
- 3mpi如何选择合适的进程数量_Redis持久化机制，优缺点，如何选择合适方式
- 4idea如何导入Gitee/GitHub项目。如何创建自己git仓库管理自己的代码。idea如何配置关联自己的仓库。_idea导入github项目
- 5第七章 案例一：分析ARP解析过程
- 6Java树表查找
- 7HarmonyOS ArkUI实战开发-NAPI 加载原理（下）
- 8Windows10家庭版 Windows defender 安全中心显示 页面不可用_你试图访问的页面不受支持,因此不可用
- 9TextView的setTextSize与xml中android:textSize属性值的对应关系_textview settextsize
- 10Node搭建后端框架【模块化，使用MySQL】_nodejs mysql框架
证明AVL树的上界和下界_证明avl树高度的上界。下界呢?
赞
踩
对于n个节点的AVL树，其高度最低的时候肯定为叶子节点只在最后一层和倒数第二层的时候。即对于 2 k − 1 < n ≦ 2 k + 1 − 1 2^k-1< n\leqq 2^{k+1}-1 2k−1<n≦2k+1−1的时候下界都为 k k k。因此下界为 h = ┌ l o g 2 ( n + 1 ) ┐ − 1 h=\ulcorner log_2(n+1)\urcorner-1 h=┌log2(n+1)┐−1
对于上界，我们可以将问题转换为高度为 h h h的树最少有多少节点。
最少的节点情况下：
我们设高度为
h
h
h的树最少节点为
S
(
h
)
S(h)
S(h)，观察不难发现
S
(
1
)
=
1
S(1)=1
S(1)=1
S ( 2 ) = 2 S(2)=2 S(2)=2
S ( h ) = S ( h − 1 ) + S ( h − 2 ) + 1 S(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
)
+
1
F(h)=S(h)+1
F(h)=S(h)+1，则上述递推式变为
F
(
1
)
=
2
F(1)=2
F(1)=2
F ( 2 ) = 3 F(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)
由线性特征根法，特征方程为 x 2 = x + 1 x^2=x+1 x2=x+1，解方程得到 x 1 = 1 − 5 2 , x 2 = 1 + 5 2 x_1=\frac{1-\sqrt{5}}{2},x_2=\frac{1+\sqrt{5}}{2} x1=21−5 ,x2=21+5
得到数列的通项为
F
(
h
)
=
A
x
1
n
+
B
x
2
n
F(h)=Ax_1^n+Bx_2^n
F(h)=Ax1n+Bx2n，带入
F
(
1
)
,
F
(
2
)
F(1),F(2)
F(1),F(2)，得到递推式为
F
(
h
)
=
5
−
3
5
10
(
1
−
5
2
)
h
+
5
+
3
5
10
(
1
+
5
2
)
h
F(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 − 3 5 10 ( 1 − 5 2 ) h + 5 + 3 5 10 ( 1 + 5 2 ) h − 1 S(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
当
h
h
h比较大的时候前一项约等于0，因此上界为
S
(
h
)
≐
5
+
3
5
10
(
1
+
5
2
)
h
−
1
S(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.44 l o g 2 ( n + 1 ) − 0.328 h=1.44log_2(n+1)-0.328 h=1.44log2(n+1)−0.328
