首页 > 建筑工程
题目内容 (请给出正确答案)
[主观题]

极端情况下,B-树中根以外所有节点只有[m/2]个分支,空间使用率大致仅有50%。而若按照教材8.2节介

绍的方法,简单地将上溢节点一分为二,则有较大的概率会出现或接近这种极端情况。

为提高空间利用率,可将内部节点的分支数下限从[m/2]提高至[2m/3]。于是,一旦节点v发生上溢且无法通过旋转完成修复,即可将v与其(已经饱和的某一)兄弟合并,再将合并节点等分为三个节点,采用这一策略之后,即得到了B-树的一个变种,称作B'-树(B'-tree)。

当然,实际上不必真地先合二为一,再一分为三。可通过更为快捷的方式,达到同样的效果:从来自原先两个节点及其父节点的共计m+(m-1)+1=2m个关键码中,取出两个上交给父节点,其余2m-2个则尽可能均衡地分摊给三个新节点。

a)按照上述思路,实现B'-树的关键码插入算法;

b)与B-树相比,B'-树的关键码删除算法又有何不同?

查看答案
答案
收藏
如果结果不匹配,请 联系老师 获取答案
您可能会需要:
您的账号:,可能还需要:
您的账号:
发送账号密码至手机
发送
安装优题宝APP,拍照搜题省时又省心!
更多“极端情况下,B-树中根以外所有节点只有[m/2]个分支,空间…”相关的问题
第1题
以下关于DOM树的论述中,哪个不正确?()

A.只有一个根节点

B.除根节点外,每个节点只有一个父节点

C.元素节点可以包含子节点

D.文本节点可以包含子节点

点击查看答案
第2题
层次模型中除了根节点以外,其它结点有且只有一个双亲结点。()
点击查看答案
第3题
在下列网络拓扑结构中,一个根节点出现故障都将影响其子节点以下所有节点故障的是_____。

A.星型拓扑

B.总线型拓扑

C.树型拓扑

D.环型拓扑

点击查看答案
第4题
在有序搜索中,如果节点x在希望树中,若x是(),则其所有子节点都在希望树中

A.终叶节点

B.端节点

C.与节点

D.或节点

点击查看答案
第5题
下列关于分支定界法中搜索树的构造的说法中正确的是()

A.根节点为0级,包含D个特征

B.每一级舍弃1个特征

C.下一级在上一级的基础上继续舍弃特征

D.整个搜索树共有D-d级

E.为避免组合重复,从左至右每个子树包含的分支依次减少

点击查看答案
第6题
试证明,采用BST::insert()算法(教材188页代码7.5),在二叉搜索树中插入节点v之后。a)除v的历代祖先以外,其余节点的高度无需更新;b)祖先高度不会降低,但至多加一;c)一旦某个祖先高度不变,更高的祖先也必然高度不变。

点击查看答案
第7题
树型目录结构的第一级称为目录树的()。A.分支节点B.根节点C.叶节点D.终节点

树型目录结构的第一级称为目录树的()。

A.分支节点

B.根节点

C.叶节点

D.终节点

点击查看答案
第8题
下面对minimax搜索算法描述中,哪句描述是不正确的()?

A.给定一个游戏搜索树,minimax算法通过每个节点的minimax值来决定最优策略

B.minimax搜索不需要遍历游戏树中所有节点

C.MIN节点希望对方收益最小化

D.MAX节点希望自己收益最大化

点击查看答案
第9题
试证明,采用BST::remove()算法(教材198页代码7.6)从二叉搜索树中删除节点,若实际被删除的节点为x,则此后:a)除x的历代祖先以外,其余节点的高度无需更新;b)祖先高度不会增加,但至多减一;c)一旦某个祖先高度不变,更高的祖先也必然高度不变。d)利用以上事实,进一步改进updateHeightAbove()方法,提高效率。

点击查看答案
第10题
解树实际是由可解节点形成的一棵子树,这棵子树的根为初始节点,叶为终止节点。()
点击查看答案
退出 登录/注册
发送账号至手机
密码将被重置
获取验证码
发送
温馨提示
该问题答案仅针对搜题卡用户开放,请点击购买搜题卡。
马上购买搜题卡
我已购买搜题卡, 登录账号 继续查看答案
重置密码
确认修改