问2-3棵树的联合？

EN

首先，不仅可以合并两个树，还可以通过一个键进行合并。因此，您将创建一个临时键，该键将大于T1中的值，小于T2中的值。

我假设T1的等级(高度)至少是T2的等级(高度)。

现在，让我们在T1上进行一次递归，以找到正确的高度来将T2插入其中。我们知道我们要合并的树应该是最右边的子树，所以在每个递归深度上有两种情况:要么这个顶点的子树与T2具有相同的等级(高度)，要么它们更高。如果我们遇到第一种情况，我们添加我们的临时键作为这个顶点的最右边，在它的右边我们添加T2，否则我们递归地使用T2合并最右边的树。然后，与另外一样，我们通过拆分具有四个关键字的顶点来保持2-3树的不变量。最后，我们从树中删除临时密钥，因此现在就有了结果。

如果关于等级(高度)的假设是相反的，那么只需执行相同的操作，但在T2上使用递归并转到最左侧的树。

如果你没有树的高度，找到高度H1和H2。找到它们需要O(log(n1))和O(log(n2))时间。您可以从根开始，转到每个节点的第一个子节点，然后计算您看到的节点，直到到达叶子。

如果它们的高度相等，则为：

创建一个新根，将其第一个子项设置为T1，第二个子项设置为T2，并假定它有一个具有适当值的键。现在删除这个虚拟密钥。使用通常的B-树删除算法，您应该在O(log )时间内获得合并的树。

如果T2的高度低于T1的高度，则为：

从T1的根目录开始。转到当前节点最右侧的子节点，H1 - H2 -1次(O(H1))。假设您在此节点中最右侧的键之后附加了一个虚拟键，则将该虚拟键之后的子指针设置为指向T2。如果这破坏了B-树的属性(如果这是第三个键)，请按照插入算法(O(H1))中固定的方式修复这些属性。您可能希望存储虚拟密钥的新位置。最后，删除虚拟密钥(O(H1))。

如果T1的高度低于T2的高度，则为：

与上一零件相同，但已镜像。(从T2开始，降到左子对象，插入到左侧，等等)

在这些情况下，您都不需要实际计算合适的虚拟密钥。您可以简单地假设它有一个适当的值，并在这些操作中忽略它的值。