动态搜索结构 动态的m路搜索树 现在我们所讨论的m路搜索树多为可以动态调 整的多路搜索树,它的一般定义为 棵m路搜索树,它或者是一棵空树,或者是满 足如下性质的树: ◆根最多有m棵子树,并具有如下的结构 n2P0,(K1,P1),(K2,P2),……,(kn,Pn) 其中,P1是指向子树的指针,0≤in<m; K是关键码,1≤i≤n<m。K1<K1≤i<n
◆在子树P1中所有的关键码都小于K1,且大于 K;,0<i<n ◆在子树Pn中所有的关键码都大于Kn; ◆在子树P0中的所有关键码都小于K1 子树P也是m路搜索树,0≤i≤n。 20.40 C d 1015 2530 4550 e 35 棵3路搜索树的示例
m路搜索树的类定义 template< class Type> class mtree{∥基类 public Triple<type> search( const Type &) protected: Node<Type> root int ma AI树是2路搜索树。如果已知m路搜索树的度m 和它的高度h,则树中的最大结点数为 (等比级数前h项求和)∑ mh+1 i=0 m-1
template <class Type> class Mtree { //基类 public: Triple<Type> & Search ( const Type & ); protected: Mnode<Type> root; int m; } 1 1 1 1 0 h h i i m m (等比级数前 h 项求和) m
每个结点中最多有m-1个关键码,在一棵高 度为h的m路搜索树中关键码的最大个数为 r+1-1 ◆对于高度h=2的二叉树,关键码最大个数为7; ◆对于高度h=3的3路搜索树,关键码最大个数 为34-1=80。 标识m路搜索树结点的三元组表示 struct Triple i Node<type>*r, ∥/结点地址指针 int i; char tag )结点中关键码序号i ∥rg=0,拽索成功;tg=1,搜索不成功
struct Triple { Mnode<Type> * r; //结点地址指针 int i; char tag; //结点中关键码序号i }; //tag=0,搜索成功；tag=1,搜索不成功
m路搜索树上的搜索算法 template <Type> Triple<Type> Mtree<Type>:: Search( const Type &x)t Triple result. 记录搜索结鼎三元组 GetNode( root ∥读入根结点 Mnode <Type> p=root, *g-=NULL; while(p!=NULL){∥从根开始检测 inti=0;key{(p-+m)+1]= MAXKEY;∥监视哨 while(p+key{计+1]<x)计++;/在结点中搜索 if(p→key计+1]==x){ ∥/搜索成功 resultr=p; result. i-i+l; result. tag =0; return result
template <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; 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; }