Exercises 18.1

tags: exercises

1. Answer:

   如果t=1,则有的节点可能没有key,那么这个节点的子节点是没有办法排序的.

2. Answer:

   t=3.

3. Answer:

   注: 有(1,2,3,4,5) key值的B-树的高度为 1.高度h满足h≤log25+12<2.

   

4. Answer:

   B-树如果每个节点都是满的,就有(1+2t+(2t)2+...+(2t)h)=(2t)h+1−12t−1个节点,每个节点有(2t−1)个keys.所以总共的keys 有f(t)=(2t)h+1−1 .

5. Answer:

   B-树的性质可以分为三类:

   1) 度的性质 : 每个节点最少有(t-1)个 key, t 个子节点; 最多 2t-1 个 key, 2t 个子节点. 2) 排序性质 : key 按升序排列, 恰好分割子树. 3) 高度性质 : 所有的叶结点有相同的高度.

   结果是一个B-树(去除nil结点).

   1. 所有叶结点有相同的高度. 因为黑结点吸收红结点,最后的结构只有黑结点,每一条路径黑结点的个数是相同的, 所以有相同的高度.

   2. 黑结点吸收红结点后也是满足排序性质的. 红黑树本身是排序的.

   3. 每个结点最少有 1 个 key , 最多只有 3 个 key, 子结点个数总是比 key 个数多 1.