求有n个结点的平衡二叉树的深度范围：
1. 求有n个结点的平衡二叉树的最小深度
显然，n个结点的平衡二叉树深度最小时，前h-1层是满的，只有最下面一层不满。这样的树类似完全二叉树，其高度也可以通过类似求n个结点完全二叉树高度的方法求出。
n个结点的这样的树的深度为
⌊
l
o
g
2
n
⌋
+
1
\lfloor log_2n \rfloor+1
⌊log2n⌋+1(见满二叉树及完全二叉树的相关性质证明)
因此n个结点的平衡二叉树深度最小值为
⌊
l
o
g
2
n
⌋
+
1
\lfloor log_2n \rfloor+1
⌊log2n⌋+1
2. 求有n个结点的平衡二叉树的最大深度
引理1：对一棵深度为h的平衡二叉树删掉一些结点后，可以得到一棵深度为 h ′ h' h′更小的平衡二叉树， h ′ h' h′是满足 h ′ < h h'<h h′<h的任意正整数。
如果原树的深度为h，其两棵子树中一定有一棵子树深度为h-1，那么删掉根结点和另一棵子树，保留深度为h-1的子树，即可以在删掉一些结点后，得到一棵深度为h-1的平衡二叉树。重复该过程，即可得到一棵深度小于原树深度的平衡二叉树。
设深度为h的平衡二叉树的最少结点数为
N
h
N_h
Nh。
引理2：已知
h
1
<
h
2
h_1<h_2
h1<h2，那么一定有
N
h
1
<
N
h
2
N_{h_1} < N_{h_2}
Nh1<Nh2。
即平衡二叉树深度h越小，构建深度为h的平衡二叉树需要用到的最少结点数目越少。
反证法：假设已知 h 1 < h 2 h_1<h_2 h1<h2，有 N h 1 ≥ N h 2 N_{h_1} \ge N_{h_2} Nh1≥Nh2。
用 N h 2 N_{h_2} Nh2个结点可以构建出一棵深度为 h 2 h_2 h2的平衡二叉树。
根据引理1，在这棵树上删掉一些结点后，可以让这棵树的深度减少，变为 h 1 h_1 h1。剩余的树上的结点数量 N ′ N' N′一定满足： N ′ < N h 2 N' <N_{h_2} N′<Nh2。
根据假设有 N h 2 ≤ N h 1 N_{h_2} \le N_{h_1} Nh2≤Nh1，所以 N ′ < N h 2 ≤ N h 1 N'<N_{h_2}\le N_{h_1} N′<Nh2≤Nh1，即 N ′ < N h 1 N'< N_{h_1} N′<Nh1
N ′ N' N′是一个深度为 h 1 h_1 h1的平衡二叉树的结点数， N ′ < N h 1 N'< N_{h_1} N′<Nh1与深度为 h 1 h_1 h1时平衡二叉树的最少结点数量为 N h 1 N_{h_1} Nh1相矛盾。
假设不成立，原命题得证。
要想使深度为h的平衡二叉树的结点最少，那么它的左右子树一定结点最少。
- 情况1：左右子树深度都为h-1，结点数都是最少的，都为 N h − 1 N_{h-1} Nh−1，加上根结点，整棵树的结点数 N h = 2 N h − 1 + 1 N_h=2N_{h-1}+1 Nh=2Nh−1+1
- 情况2：左右子树深度之差为1，即一个子树深度是h-1，另一个子树深度是h-2，整棵树的结点数 N h = N h − 1 + N h − 2 + 1 N_h=N_{h-1}+N_{h-2}+1 Nh=Nh−1+Nh−2+1
根据引理2，有
N
h
−
2
<
N
h
−
1
N_{h-2} < N_{h-1}
Nh−2<Nh−1，
所以深度为h的平衡二叉树结点数最少时，左右子树深度一定不同，相差1，有
N
h
=
N
h
−
1
+
N
h
−
2
+
1
N_h=N_{h-1}+N_{h-2}+1
Nh=Nh−1+Nh−2+1
对于有n个结点的平衡二叉树，如果n满足 N h ≤ n < N h + 1 N_h\le n < N_{h+1} Nh≤n<Nh+1，那么n个结点可以构建的平衡二叉树的最大深度为h。
解释：
要构建深度为h的平衡二叉树最少需要 N h N_h Nh个结点，现在有n（ n ≥ N h n\ge N_h n≥Nh）个结点，可以构建深度为h的平衡二叉树。
如果要构建深入为h+1的平衡二叉树，最少需要 N h + 1 N_{h+1} Nh+1个结点，n个结点还不够。
所以如果 N h ≤ n < N h + 1 N_h\le n < N_{h+1} Nh≤n<Nh+1，n个结点可以构建的平衡二叉树的最大深度为h。
设斐波那契数列第i项为
F
i
F_i
Fi，已知
F
1
=
1
,
F
2
=
1
,
F
3
=
2
,
.
.
.
F_1=1, F_2=1, F_3=2,...
F1=1,F2=1,F3=2,...
证明：
N
h
=
F
h
+
2
−
1
N_h=F_{h+2}-1
Nh=Fh+2−1
数学归纳法证明
- N 1 = 1 = F 3 − 1 N_1=1=F_3-1 N1=1=F3−1
- 假设 N h = F h + 2 − 1 N_h=F_{h+2}-1 Nh=Fh+2−1，证明 N h + 1 = F h + 3 − 1 N_{h+1}=F_{h+3}-1 Nh+1=Fh+3−1
N h + 1 N_{h+1} Nh+1
= N h + N h − 1 + 1 =N_h+N_{h-1}+1 =Nh+Nh−1+1
= F h + 2 − 1 + F h + 1 − 1 + 1 =F_{h+2}-1+F_{h+1}-1+1 =Fh+2−1+Fh+1−1+1
= F h + 2 + F h + 1 − 1 =F_{h+2}+F_{h+1}-1 =Fh+2+Fh+1−1
= F h + 3 − 1 =F_{h+3}-1 =Fh+3−1
已知
N
h
≤
n
<
N
h
+
1
N_h\le n < N_{h+1}
Nh≤n<Nh+1，因此
F
h
+
2
−
1
≤
n
<
F
h
+
3
−
1
F_{h+2}-1\le n < F_{h+3}-1
Fh+2−1≤n<Fh+3−1
n个结点构成的平衡二叉树的最大深度的精确数值通过数学公式很难计算，这里给出算法：
通过递推算法先求出斐波那契数列，枚举每个斐波那契数，得到第一个满足大于n+1的斐波那契数，这个数是斐波那契数列的第i项，那么n个结点构成的平衡二叉树的最大深度为i-3。文章来源：https://www.toymoban.com/news/detail-742271.html
#include<bits/stdc++.h>
using namespace std;
int main()
{//输入结点数量n，输出n个顶点可以构成的平衡二叉树的最大深度
int n, a = 2, b = 3, t;
cin >> n;//结点数量n一定是正整数
for(int i = 4; true; ++i)//当前b是斐波那契数列第i项
{
if(b > n+1)
{
cout << i-3;
return 0;
}
b = b+a;//最后求出的斐波那契数
a = b-a;
}
return 0;
}
3. 有n个结点的平衡二叉树的深度的数量级
当n很大时，估算h的数量级：
平衡二叉树深度最小时，深度为
⌊
l
o
g
2
n
⌋
+
1
\lfloor log_2n \rfloor+1
⌊log2n⌋+1，其数量级为
O
(
l
o
g
n
)
O(logn)
O(logn)
平衡二叉树深度最大时：
已知
F
h
+
2
−
1
≤
n
<
F
h
+
3
−
1
F_{h+2}-1\le n < F_{h+3}-1
Fh+2−1≤n<Fh+3−1
那么
F
h
+
2
≤
n
+
1
<
F
h
+
3
F_{h+2}\le n+1 < F_{h+3}
Fh+2≤n+1<Fh+3
根据斐波那契数列的通项公式：
F
n
=
1
5
(
(
1
+
5
2
)
n
−
(
1
−
5
2
)
n
)
F_n = \frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n)
Fn=51((21+5)n−(21−5)n)，
由于
∣
1
−
5
∣
<
2
|1-\sqrt{5}|<2
∣1−5∣<2，所以当n很大时，
(
1
−
5
2
)
n
(\frac{1-\sqrt{5}}{2})^n
(21−5)n趋近于0。
因此可以认为：
F
n
≈
1
5
(
1
+
5
2
)
n
F_n \approx \frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n
Fn≈51(21+5)n
记
ϕ
=
1
+
5
2
\phi=\frac{1+\sqrt{5}}{2}
ϕ=21+5，有
ϕ
h
+
2
≤
5
(
n
+
1
)
<
ϕ
h
+
3
\phi^{h+2}\le \sqrt{5}(n+1) <\phi^{h+3}
ϕh+2≤5(n+1)<ϕh+3
取对数
h
+
2
≤
l
o
g
ϕ
5
(
n
+
1
)
<
h
+
3
h+2\le log_\phi{\sqrt{5}(n+1)}<h+3
h+2≤logϕ5(n+1)<h+3
有：
l
o
g
ϕ
5
(
n
+
1
)
−
3
<
h
≤
l
o
g
ϕ
5
(
n
+
1
)
−
2
log_\phi{\sqrt{5}(n+1)} -3< h \le log_\phi{\sqrt{5}(n+1)}-2
logϕ5(n+1)−3<h≤logϕ5(n+1)−2
树深度h的数量级为：
O
(
h
)
=
O
(
l
o
g
ϕ
5
(
n
+
1
)
−
2
)
=
O
(
log
ϕ
5
+
l
o
g
ϕ
(
n
+
1
)
)
=
O
(
l
o
g
n
)
O(h)=O(log_\phi{\sqrt{5}(n+1)}-2)=O(\log_\phi{\sqrt{5}+log_\phi(n+1)})=O(log n)
O(h)=O(logϕ5(n+1)−2)=O(logϕ5+logϕ(n+1))=O(logn)
因此，有n个结点的平衡二叉树的深度的数量级为
O
(
l
o
g
n
)
O(log n)
O(logn)文章来源地址https://www.toymoban.com/news/detail-742271.html
到了这里，关于有n个结点的平衡二叉树的最小、最大深度，及深度的数量级的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
