赞
踩
对这题答案,是完全出乎意外的,可见这块知识,应该是全未知。真得需要一个过程。
答案:根据 b树的限定 关键字的取值范围,可以得到 m/2(上取整)-1=13 -1
=12
b树全称Balance-tree(平衡多路查找树),在数据结构复习之树表查找,只涉及到了二叉排序树,但没有涉及到平衡二叉树,所以直接过渡到B树的话,理解起来是有一定的跨度的。要想明白B树,先要理解平衡二叉树。
平衡:其实就是指左右均衡。平衡二叉树又被称为AVL树
它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
解决了二叉排序树退化成链表的问题,把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。从这点来说,要比二叉排树稳定;还是挺有实际意义的。
平衡二叉树大部分操作和二叉查找树类似,主要不同在于插入删除的时候平衡二叉树的平衡可能被改变。
把需要重新平衡的结点叫做α,由于任意两个结点最多只有两个儿子,因此高度不平衡时,α结点的两颗子树的高度相差2.容易看出,这种不平衡可能出现在下面4中情况中:
对于第1和4的情况下,插入发生在“外侧”,只需要通过一侧旋转即可
为使树恢复平衡,我们把k2变成这棵树的根节点,因为k2小于k1,把k1置于k2的右子树上,而原本在k2右子树的Y小于k1,k2,就把Y置于k1的左子树上,这样既满足了二叉查找树的性质,又满足了平衡二叉树的性质。图示所示的情形为左左,那么就右旋;这里要明白,从哪里开始右旋??从两边哪里开始不一样的,就从哪里开始旋?左孩子的左孩子,再插入一个结点的话,那就是从第1个左孩子不一样了,所以从第1个左开始右旋,即从左孩子k2右旋,变成根。
对于2和3插入发生在“内侧”情形下,则需要两侧旋转才能完成。
第一步,把k2作为根,进行一次左旋转,旋转之后就变成了左左情况,所以第二步再进行一次右旋转,最后得到了一棵以k2为根的平衡二叉树树。同理,图示情形为左孩子的右孩子插入新结点情形,那么就先左旋???两边从哪里不一样的?从右孩子开始不一样,所以k2左旋变为根,以下类似
了解这些就够了,注意:森林、树与二叉树转换不同;详见:数据结构复习之线索二叉树 森林与二叉树相互转化,兄弟变为右孩子的思路是不同的,需要有连线操作。
b树也是平衡树,但是多路的,不再像平衡二叉树只有两个分支结点了。b树的父结点有多个孩子结点。
阶其实指非叶子结点的子结点的个数,也就是最多的查找路径;M阶=M路,当M=2则是2叉树,M=3则是3叉;实际上没有m=2,因为2阶b树其实就是平衡二叉树。一般m阶树指的都是m>=3的情形。
b树的信息域(n,Ai,Ki,Ai+1…);Ki指的是关键字(本结点存储的关键字),并且前一个关键字小于后一个关键字的值,类似于平衡二叉树里的结点的值。最前面的n指的是本结点存储关键字的个数.;Ai为指向孩子结点的指针,且孩子结点里关键字值都小于Ki+1
2个子结点指针+1个关键字 这种数据结构,不就是二叉排序树的数据结构吗?平衡二叉树不过是人为规定了“每个非叶子结点都有两个孩子结点,并且子树的高度之差绝对值不大于1”,所以就有了“平衡”之说。
b树也是在二叉排序树的基础上得来的,只不过不同于平衡二叉树,人为规定使之平衡,而是使用扩展2+1这种数据结构的方式,使关键字个数不再为1了,而是可以最多到m-1.孩子结点最多可以是m;这样,一来可以存储的更多,并且由于是部分线性存储,可以查找更方便,二来,也不再规定子树高度值,而是直接将叶子结点放在同一层。这样就实现了平衡。
由上面平衡可知,m阶对于b树是一种限定。
孩子结点取值是 m/2(上取整) <= Ai <= m
关键字个数取值(比孩子结点取值少1个) m/2(上取整)-1 <= Ki <= m-1
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。