算法导论 18-2 连接与分裂2-3-4树
CLRS 18-2
连接与分裂2-3-4树
连接操作的输入为两个动态集合S’和S”，以及一个元素x，使得对任何x’ε S’，x” ε S”，有key[x’] < key[x] < key[x”]。它返回一个集合S = S’ U {x} U S”。分裂操作有点像一个“逆”操作：给定一个动态集S和一个元素xε S，它创建一个集合S’，其中包含了S – {x}中所有关键字小于key[x]的元素；同时创建了一个集合S”，网站空间，其中包含了S – {x}中所有关键字大于key[x]的元素。在这个问题中，我们来讨论如何在2-3-4树上实现这些操作。为方便起见，假定所有元素都只包含关键字，而且所有的关键字都不相同。
a)对2-3-4树中的每个结点x，说明如何将以x为根的子树的高度作为一个域height[x]来维护。要注意所给出的实现不应影响查找、插入和删除操作的渐进运行时间。
P270中，“对根进行分裂是增加B树高度的唯一途径”，插入结点时，只有当根分裂时，新产生的那个结点的高度为其子节点的高度加1。而对于删除结点的操作，当合并根节点的子节点时，根节点消失，其他结点的高度保持不变。(注意这里是结点，香港虚拟主机，不要把结点和结点内的元素混淆了)
b)说明如何实现联结操作。给定两个2-3-4树T’和T”以及一个关键字k，连接操作的运行时间应是O(1 + |h’ – h”|)，其中h’和h”分别为T’和T”的高度。
当h’ > h”时，在树T’中高度为h”的最右结点中插入k及树T”，当然从T’的根节点到这里的路径中，进行必要的分裂操作。
当h” > h’时，亦然。
c)考虑从一棵2-3-4树T的根至一个给定的关键字k的路径p，包含T中小于k的关键字集合S’，以及包含T中大于k的关键字的集合S”。证明p将S’分裂成一个树的集合{T0′, T1′, …, Tm’}和一个关键字的集合{k1′, k2′, …, km’}，此处对每个i = 1, 2, …, m，以及任何关键字yε Ti-1′ 和zε Ti’，香港服务器租用，都有y < k1′ < z。Ti-1’和Ti’的高度之间有什么关系？请说明p是如何将S”分裂成树的集合和关键字的集合的。
Ti-1’和Ti’的高度之间关系：h(Ti-1′) = h(Ti’) + 1
p将S”分裂成一个树的集合{T0”, T1”, …, Tm”}和一个关键字的集合{k1”, k2”, …, km”}，此处对每个i = 1, 2, …, m，以及任何关键字yε Ti-1” 和zε Ti”，都有y > k1′ > z。
d)请说明如何实现T上的分裂操作。利用联结操作将S’中的关键字拼成一棵2-3-4树T’，将S”中的关键字拼成一棵2-3-4树T”。分裂操作的运行时间为O(lgn)，此处n为T中的关键字个数。（提示：连接的代价应该是套迭的）
从根节点，开始寻找元素x，所得寻找路径将原树T分为左右两半，即可得集合S’和S”，由于t=2，且路径最大长度为树的高度，故运行时间为O(lgn).
posted on
读书须用意，一字值千金。
