算法导论-18-2-连接与分裂2-3-4树

a）

插入操作：

一个结点分裂时，分裂出一个新的结点，新结点和原结点的高度是相同的。因此分裂不会改变结点的高度。结点的高度在它生成时就确定的，不会因为分裂而调度增加。

树的高度增加的唯一方式是根结点的分裂。根结点分裂时，除了产生一个与根结点高度相同的结点外，还会产生一个新的根结点，新的根结点的高度是原根结点的高度+1

删除操作：

删除一个关键字时，或者把父结点的关键字补到结点中，或者合并，都不会影响结点的高度。树的高度减小的唯一方式是根结点的两个孩子合并，根结点删除。

height[x]的处理方式：

普通结点分裂时，将新结点的height[x]置为原结点的height。根结点分裂时，新的根结点的height[x]置为原结点的height+1。

其余情况不需要处理。

b）

若h'=h''，k做为根结点，T‘和T''分别作为它的孩子

若h'>h''，在T'中找到高度为h''的最右结点边，在结点中插入关键字k和树T’‘，如果有必要，进行分裂

若h''>h'，反之亦然。

c）

高度关系：？

p将S'分裂成一个树的集合{T0', T1', ……, Tm'}和一个关键字集合{k1', k2', ……, km'}，此处对每个i=1, 2, ……, m，以及任何关键字y属于T(i-1)'和z属于Ti'，都有y>k1'>z。

d）不懂