简述网站建设和推广评价指标,海纳网站建设,成都seo经理,网站代运营服务内容有7.4.1_1 B树
5叉查找树
//5叉排序树的结点定义
struct Node {ElemType keys[4]; //最多4个关键字struct Node child[5]; //最多5个孩子int num; //结点中有几个关键字
}; 如何保证查找效率#xff1f; eg:对于5叉排序树#xff0c;规定…7.4.1_1 B树
5叉查找树
//5叉排序树的结点定义
struct Node {ElemType keys[4]; //最多4个关键字struct Node child[5]; //最多5个孩子int num; //结点中有几个关键字
}; 如何保证查找效率 eg:对于5叉排序树规定除了根节点处。任何结点都至少有3个分叉2个关键字
策略: ①m叉查找树中规定除了根节点外任何结点至少有个分叉即至少含有个关键字 ②m叉查找树中规定对于任何一个结点其所有子树的高度都要相同。
7.4.1 B树
B树又称多路平衡查找树B树中所被允许的孩子个数的最大值称为B树的阶通常用m表示。一棵m阶B树或为空树或为满足如下特性的m叉树: 1)树中每个结点至多有m棵子树即至多含有m-1个关键字。 2)若根结点不是终端结点则至少有两棵子树。 3)除根结点外的所有非叶结点至少有棵子树即至少含有个关键字。 5)所有的叶结点都出现在同一层次上并且不带信息可以视为外部结点或类似于折半查找判定树的查找失败结点实际上这些结点不存在指向这些结点的指针为空)。
7.4.1_2 B树的插入和删除
B树的插入
7.4.1_3 B树
一棵m阶的B树需满足下列条件: 1每个分支结点最多有m棵子树(孩子结点)。 2非叶根结点至少有两棵子树其他每个分支结点至少有「m/2]棵子树。 3结点的子树个数与关键字个数相等。 4所有叶结点包含全部关键字及指向相应记录的指针叶结点中将关键字按大小顺序排列并且相邻叶结点按大小顺序相互链接起来。 5所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。 B树 VS B树 m阶B树: 1)结点中的n个关键字对应n棵子树 2)根节点的关键字数n∈[1, m] 其他结点的关键字数 3)在B树中叶结点包含全部关键字,非叶结点中出现过的关键字也会出现在叶结点中 4在B树中叶结点包含信息所有非叶结点仅起索引作用非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针不含有该关键字对应记录的存储地址。
m阶B树: 1)结点中的n个关键字对应n1棵子树 2)根节点的关键字数n∈[1, m-1]。 其他结点的关键字数 3)在B树中各结点中包含的关键字是不重复的 4)B树的结点中都包含了关键字对应的记录的存储地址
在B树中非叶结点不含有该关键字对应记录的存储地址。 可以使一个磁盘块可以包含更多个关键字使得B树的阶更大树高更矮 读磁盘次数更少查找更快
