首页 > 试题广场 >

A 3-order B-tree has 2047 key

[单选题]
A 3-order B-tree has 2047 key words,what is the maximum height of the tree?
  • 11
  • 12
  • 13
  • 14
答案:A
M阶B树只能在叶子结点存储数据,其他结点的孩子个数必须在[ceiling(M/2), M]之间,根节点要么是叶子结点,要么至少有两个孩子。 
根据该定义,如果3阶B树有2048个元素,那高度最大时每个结点都取孩子个数下限(2),高度为12(即log(2048)+1)。 
然后去掉一个叶子结点,则从叶子向根一路发生结点合并,一个2孩子结点和一个1孩子结点合并成为一个3孩子结点。 
根节点的两个孩子也发生了结点合并,变成了一个结点,根不再满足B树的要求,被删除,其唯一的孩子成为了新的根。 于是,树的高度变为了11。 


发表于 2015-01-27 15:04:55 回复(0)