q=p;p=ppt;∥向下一层结点搜索 GetNode(p) 读入该结点 resultr=g; result. i=i; result. tag return result ∥搜索失败,返回插入位置 提高搜索树的路数m,可以改善树的搜索性能。 对于给定的关键码数n,如果搜索树是平衡的 可以使m路搜索树的性能接近最佳。下面我们 将讨论一种称之为B树的平衡的m路搜索树。 在B树中我们引入“失败”结点。一个失败结 点是当搜索值x不在树中时才能到达的结点
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_树中我们引入“失败”结点。一个失败结 点是当搜索值x不在树中时才能到达的结点
B树 一棵m阶B树是一棵m路搜索树,它或者是 空树,或者是满足下列性质的树 根结点至少有2个子女。 0除根结点以外的所有结点及失败结点至少有 「m21个子女。 所有的失败结点都位于同一层。 事实上,在B树的每个结点中还包含有一组指 针Dm,指向实际对象的存放地址。K与D (1≤isn<m)形成一个索引项(Ki,D[i,通过 K订可找到某个对象的存储地址D[引
B_树 一棵 m 阶B_树是一棵 m 路搜索树，它或者是 空树，或者是满足下列性质的树： 根结点至少有 2 个子女。 除根结点以外的所有结点及失败结点至少有 m/2 个子女。 所有的失败结点都位于同一层。 事实上，在B_树的每个结点中还包含有一组指 针D[m]，指向实际对象的存放地址。K[i]与D[i] (1 i n < m)形成一个索引项(K[i], D[i])，通过 K[i]可找到某个对象的存储地址D[i]
4 15125301450 35 1015 25135 非B树 B树 B树的类定义和B树结点类定义 template <class Type> class Btree: public Mtree<Type>( ∥/继承m路搜索树的所有属性和操作
非B_树 B_树 B_树的类定义和B_树结点类定义 template <class Type> class Btree : public Mtree<Type> { //继承 m 路搜索树的所有属性和操作
publi Ic int Insert( const Type&x ) int Remove( const Type&x ) template< class Type> class node{∥点定义 private: int n. ∥结点中关键码个数 Vnodes iypes *parent /亲指针 Type key(m+ll )关键码数组1~m-1 Node<Iype>ptr[m+1];/树指针数组0~m
public: int Insert ( const Type& x ); int Remove ( const Type& x ); }; template <class Type> class Mnode { //结点定义 private: int n; //结点中关键码个数 Mnode<Type> *parent; //双亲指针 Type key[m+1]; //关键码数组1m-1 Mnode<Type> *ptr[m+1]; //子树指针数组0m };
B树的搜索算法 B树的搜索算法继承了在m路搜索树Mree上的 搜索算法。 B树的搜索过程是一个在结点内搜索和循某 条路径向下一层搜索交替进行的过程。因此, B树的搜索时间与B树的阶数m和B树的高度 h直接有关,必须加以权衡。 在B树上进行搜索,搜索成功所需的时间取决 于关键码所在的层次,搜索不成功所需的时间 取决于树的高度。如果我们定义B树的高度h 为失败结点所在的层次,需要了解树的高度h与 树中的关键码个数N之间的关系
B_树的搜索算法 B_树的搜索算法继承了在m路搜索树Mtree上的 搜索算法。 B_树的搜索过程是一个在结点内搜索和循某一 条路径向下一层搜索交替进行的过程。因此， B_树的搜索时间与B_树的阶数m和B_树的高度 h直接有关，必须加以权衡。 在B_树上进行搜索，搜索成功所需的时间取决 于关键码所在的层次，搜索不成功所需的时间 取决于树的高度。如果我们定义B_树的高度h 为失败结点所在的层次，需要了解树的高度h 与 树中的关键码个数 N 之间的关系