当前位置：首页 > ai >正文

算法C实现--第16章习题集-外部查找

ai 2025/6/17 12:09:55

持续更新中

16.7 Give the height of the B trees that result when you insert the keys 562, 221, 240, 771, 274, 233, 401, 273, 201 in Exercise 16.28 in that order into an initially empty tree, for each value of $M > 2$ .

Exercise1607

目标：直观上感受下B树高度和节点数、阶数之间的关系。

理论关系：
$\log_{M}N\leq H \leq\log_{M/2}N$
这个公式告诉我们，树高与 $M$ 的对数成反比。当 $M$ 越大，树能够容纳的键越多，树高就越低。

运行结果

M = 3, 插入完成，节点总数 N = 9，B 树高度 H = 3
M = 4, 插入完成，节点总数 N = 9，B 树高度 H = 2
M = 5, 插入完成，节点总数 N = 9，B 树高度 H = 1
M = 6, 插入完成，节点总数 N = 9，B 树高度 H = 1
M = 7, 插入完成，节点总数 N = 9，B 树高度 H = 1
M = 8, 插入完成，节点总数 N = 9，B 树高度 H = 1
M = 9, 插入完成，节点总数 N = 9，B 树高度 H = 1
M = 10, 插入完成，节点总数 N = 9，B 树高度 H = 0

汇总分析：

M	理论最小高度 $log_M N$	理论最大高度 $log_{M/2} N$	实际高度 H
3	$log_3 9 = 2$	$\log_{1.5} 9 \approx 4.82$	3
4	$\log_4 9 \approx 1.58$	$\log_2 9 \approx 3.17$	2
5	$\log_5 9 \approx 1.37$	$\log_{2.5} 9 \approx 2.32$	1
6	$\log_6 9 \approx 1.22$	$log_3 9 = 2$	1
7	$\log_7 9 \approx 1.12$	$\log_{3.5} 9 \approx 1.93$	1
8	$\log_8 9 \approx 1.05$	$\log_4 9 \approx 1.58$	1
9	$log_9 9 = 1$	$\log_{4.5} 9 \approx 1.47$	1
10	$\log_{10} 9 \approx 0.95$	$\log_5 9 \approx 1.37$	0