AVL树是2路搜索树。若已知m路搜索树的 度m和它的高度h,则树中的最大结点数为 (等比级数前h项求和)∑m2=-1,、(m4-1) =0 m 每个结点中最多有m-1个关键码,在一棵高 度为h的m路搜索树中关键码的最大个数为 nr+1-1 ◆高度h=2的二叉树,关键码最大个数为7 高度h=3的3搜索树,关键码最大个数为 34-1=80。 16
16 AVL树是2路搜索树。若已知m 路搜索树的 度 m 和它的高度 h, 则树中的最大结点数为 ( 1) 1 1 1 0 − − = + = h h i i m m (等比级数前 h 项求和) m 每个结点中最多有 m-1 个关键码，在一棵高 度为 h 的 m 路搜索树中关键码的最大个数为 mh+1 -1。 ◆ 高度 h=2 的二叉树, 关键码最大个数为7； ◆ 高度 h=3 的3路搜索树, 关键码最大个数为 3 4-1 = 80
m路搜索树上的搜索 在m路搜索树上的搜索过程是一个在结点 内搜索和自根结点向下逐个结点搜索的交 替的过程。 700t a20140」搜索35 b 1015c2530 4550 e35 17
17 m 路搜索树上的搜索 ◼ 在 m 路搜索树上的搜索过程是一个在结点 内搜索和自根结点向下逐个结点搜索的交 替的过程。 35 a 20 40 b c d e 10 15 25 30 45 50 root 搜索35
提高搜索树的路数m,可以改善树的搜索性 能。对于给定的关键码数n,如果搜索树 是平衡的,可以使m路搜索树的性能接近 最佳。下面将讨论一种称之为B树的平衡 的m路搜索树。 18
18 ◼ 提高搜索树的路数 m, 可以改善树的搜索性 能。对于给定的关键码数 n，如果搜索树 是平衡的，可以使 m 路搜索树的性能接近 最佳。下面将讨论一种称之为B 树的平衡 的 m 路搜索树
B树 棵m阶B树是一棵平衡的m路搜索树,它 或者是空树,或者是满足下列性质的树 根结点至少有2个子女。 ◆除根结点以外的所有结点(不包括失败结 点至少有「m2个子女。 ◆所有的失败结点都位于同一层。 在B树中的“失败”结点是当搜索值不在 树中时才能到达的结点。该层计入树的高度。 事实上,在B树的每个结点中还包含有一组 指针Dm,指向实际对象的存放地址
19 B 树 ◼ 一棵 m 阶 B 树是一棵平衡的 m 路搜索树, 它 或者是空树, 或者是满足下列性质的树： ◆ 根结点至少有 2 个子女。 ◆ 除根结点以外的所有结点 (不包括失败结 点)至少有 m/2 个子女。 ◆ 所有的失败结点都位于同一层。 ◼ 在 B 树中的“失败”结点是当搜索值x不在 树中时才能到达的结点。该层计入树的高度。 ◼ 事实上，在 B 树的每个结点中还包含有一组 指针D[m]，指向实际对象的存放地址
K与D团(1≤i≤n<m)形成一个索引项 (K[i,Di),通过K可找到某个对象的存 储地址Di。 一棵B树是平衡的m路搜索树,但一棵平 衡的m路搜索树不一定是B树。 700t I root 非B树2040 B树 30 10152530、4550 20 35 101525 354550
20 30 ◼ K[i]与D[i] (1 i n < m) 形成一个索引项 (K[i], D[i])，通过K[i]可找到某个对象的存 储地址D[i]。 ◼ 一棵 B 树是平衡的 m 路搜索树，但一棵平 衡的 m 路搜索树不一定是 B 树。 35 20 40 10 15 25 30 45 50 root 35 45 50 20 40 root 10 15 25 非B 树 B 树