每个结点中最多有m-1个关键码,在一棵 高度为h的m路搜索树中关键码的最大个 数为m1+1-1。 ◆高度h=2的二叉树,关键码最大个数为7; ◆高度h=3的3路搜索树,关键码最大个数 为34-1=80。 标识m路搜索搜索结果的三元组表示 struct Triple i Mnde<Iype>*r;结点地址指针 int 1; int tag ∥/结点中关键码序号i tag=0,搜索成功;tag=1,搜索不成功
◼ 每个结点中最多有 m-1 个关键码，在一棵 高度为 h 的 m 路搜索树中关键码的最大个 数为 mh+1 -1。 ◆ 高度 h=2 的二叉树, 关键码最大个数为7； ◆ 高度 h=3 的3路搜索树, 关键码最大个数 为 3 4-1 = 80。 struct Triple { Mnode<Type> * r; //结点地址指针 int i; int tag; //结点中关键码序号 i }; //tag=0,搜索成功；tag=1,搜索不成功 标识 m 路搜索树搜索结果的三元组表示
m路搜索树上的搜索算法 在m路搜索树上的搜索过程是一个在结点 内搜索和自根结点向下逐个结点搜索的交 替的过程。 700t a2040、搜索35 1015c2530小d4550 e35
m 路搜索树上的搜索算法 ◼ 在 m 路搜索树上的搜索过程是一个在结点 内搜索和自根结点向下逐个结点搜索的交 替的过程。 35 a 20 40 b c d e 10 15 25 30 45 50 root 搜索35
template <class Type> Triple< type> Mtree<Type>:: Search( const Type& x)i Triple result, 记录搜索结果三元组 GetNode(root);/读入根结点 Mnode <Type>*p= root, *q= NULL; while(pl=NULL){∥从根开始检测 int i=0; p->key[(p->n)+1= MAXKEY: 鹗 while(p>keyi+1<x)i+t;∥结点内搜 if (p->key[i+1]=x)f 搜索成功 result. r-p; result. i-1+l; result. tag =0; return result
template <class Type> Triple<Type> & Mtree<Type> :: Search ( const Type& x ) { Triple result; //记录搜索结果三元组 GetNode ( root ); //读入根结点 Mnode <Type> *p = root, *q = NULL; while ( p != NULL ) { //从根开始检测 int i = 0; p->key[(p->n)+1] = MAXKEY; while ( p->key[i+1] < x ) i++; //结点内搜 索 if ( p->key[i+1] == x ) { //搜索成功 result.r = p; result.i = i+1; result.tag = 0; return result; }
q=p;p=p->ptri];/1下一层结点搜索 GetNode (p) ∥/读入该结点 result. r-g: result. i-i; result. tag =l; return result;∥/搜索失败,返回插入位置 提高搜索树的路数m,可以改善树的搜索性 能。对于给定的关键码数n,如果搜索树是 平衡的,可以使m路搜索树的性能接近最佳。 下面将讨论一种称之为B树的平衡的m路搜 索树
q = p; p = p->ptr[i]; //向下一层结点搜索 GetNode (p); //读入该结点 } result.r = q; result.i = i; result.tag = 1; return result; //搜索失败,返回插入位置 } ◼ 提高搜索树的路数 m, 可以改善树的搜索性 能。对于给定的关键码数 n，如果搜索树是 平衡的，可以使 m 路搜索树的性能接近最佳。 下面将讨论一种称之为B 树的平衡的 m 路搜 索树
B树 棵m阶B树是一棵平衡的m路搜索树,它 或者是空树,或者是满足下列性质的树 根结点至少有2个子女。 ◆除根结点以外的所有结点(不包括失败结 点至少有「m/21个子女。 ◆所有的失败结点都位于同一层。 在B树中的“失败”结点是当搜索值不在 树中时才能到达的结点。 事实上,在B树的每个结点中还包含有一组 指针Dm,指向实际对象的存放地址
B 树 ◼ 一棵 m 阶B 树是一棵平衡的 m 路搜索树, 它 或者是空树, 或者是满足下列性质的树： ◆ 根结点至少有 2 个子女。 ◆ 除根结点以外的所有结点 (不包括失败结 点)至少有 m/2 个子女。 ◆ 所有的失败结点都位于同一层。 ◼ 在B 树中的“失败”结点是当搜索值x不在 树中时才能到达的结点。 ◼ 事实上，在B 树的每个结点中还包含有一组 指针D[m]，指向实际对象的存放地址