算法导论 第18章 思考题18-2 2-3-4树的链接与分裂，推广至B树_算法导论18-2

题目

    2-3-4树是B树的特例，是度为2的B树。在B树这篇博客中，我们实现的B树是一个模板，因此要得到2-3-4树，即度为2的B树非常容易，只要如是声明就可以了——Btree<int,2> bt，其中int是所存元素类型。

    在本题中，要实现的是2-3-4树的链接与分裂。参看红黑树的连接操作我们不难得到2-3-4树的链接方法。现在，我们对于2-3-4树的链接也予以推广，即实现任意度数的B树的链接和分裂。

(a)

   B树高度的变化只有两种方式：一是在插入关键字的时候，根节点满，那么其要分裂，树长高；二是在删除关键字的时候，关键字不在内节点，根节点只有一个关键字，且左右孩子均已达到最小关键字数，那么将会合并根唯一的关键字和左右孩子，树高将减1。

   因此，在节点增加height域后。在insert中树长高时，将新树根的高设为旧根高再加1（root->height = p->height + 1;）代码请参看B树实现，下同；在erase_aux函数中，代码不用更改，因为旧根会被释放，直接指向孩子，该孩子将成为新根。

(b) 假设将树T'链接到树T上，链接关键字为k，且满足条件任意key[T] < k < key[T']，key[T] > k > key[T']类似。

   为便于讨论，先抛出相关函数名称。

1.   nodeAtRightOfHeight(size_t h):在树T中找到高度为h的最右侧节点的父亲；
2.   nodeAtLeftOfHeight(size_t h):在树T中找到高度为h的最左侧节点的父亲；
3.   linkAtRight(k,T'):在树T的右侧连接T'和k；
4.   linkAtLeft(k,T'):在树T的左侧链接T'和k。

若树T较T'高，

  1、调用nodeAtRightOfHeight在树T右侧找到和树T'一样的节点；

  2、在查找过程中，对于已满节点，即关键字数目已达到2*degree - 1的节点，对其调用split函数予以分裂；

  3、找到该节点的父亲，然后直接将k插入父节点，作为最末关键字，将树T'整个作为k的右孩子，完成合并。由于只要是满节点则分裂，故此时父节点不可能满。

若树T和T'高度一样，

   1、构造新根，插入关键字k，将T,T'分别作为该节点的左右孩子，更新相关域，合并完毕。

   以上两种情况调用linkAtRight;

若树T较T'矮，

   1、交换两树；

   2、调用linkAtLeft将交换后的树T'和k从左侧链接到交换后的树T上，该过程和第一种情况对称。

时间复杂度分析：

    显然，对于2-3-4树，树高是O(lgn)，故每次下降查找的次数为O(lgn)。对于每一次，即使存在分裂的情况以调用sp