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