」每个结点中最多有m-1个关键码,在一棵 高度为h的m路搜索树中关键码的最大个 数为m+11。 ◆高度h=2的二叉树,关键码最大个数为7; 高度h=3的3路搜索树,关键码最大个数 为341=80。 标识m路搜索树搜索结果的三元组表示 struct Triple i Node<Type>*r;M结点地址指针 int 1; int tag: ∥/结点中关键码序号i tag=0,搜索成功;tag=1,搜索不成功
struct Triple { Mnode<Type> * r; //结点地址指针 int i; int tag; //结点中关键码序号 i }; //tag=0,搜索成功；tag=1,搜索不成功
m路搜索树上的搜索算法 」在m路搜索树上的搜索过程是一个在结点 内搜索和自根结点向下逐个结点搜索的交 替的过程。 700t a20140、搜索35 b1015 C2530 4550 e35
35 a 20 40 b c d e 10 15 25 30 45 50 root
template <class Type> Triple<type> Mtree<Type>:: Search( const Type& xi Triple result ∥/记录搜索结果三元组 GetNode(root);/读入根结点 Mnode <Type>p=root, * q=nULl while(pl=NULL){∥从根开始检测 int 1=0; p->key[(p-)n)+1= MAXKEY while(p-keyi+l<x)i++;/结点内搜索 if(p)keyi+11=x){搜索成功 result. r-p; result. i=1+l; result. tag=0; return results
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-pti;下一层结点搜索 GetNode (p) ∥/读入该结点 result. r-g: result. 1=1; result. tag =1; 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; //搜索失败,返回插入位置 }
B树 J一棵m阶B树是一棵平衡的m路搜索树,它 或者是空树,或者是满足下列性质的树: ◆根结点至少有2个子女。 ◆除根结点以外的所有结点(不包括失败结 点至少有「m/21个子女。 ◆所有的失败结点都位于同一层。 在B树中的“失败”结点是当搜索值x不在 树中时才能到达的结点 事实上,在B树的每个结点中还包含有一组 指针Dm,指向实际对象的存放地址