我正在寻找一种方法来合并两个 2-3 束，而不是仅仅在其中一个上重复调用插入（如果可能的话，在 O(n+m) 时间内）。在 BST 中，您只需按顺序遍历它们，将键存储到数组中，然后合并数组并从排序的数组 od 键中构建完美平衡的 BST。
但我真的不知道如何从排序的键数组中构建一个 2-3 树，因为完美平衡的 BST 通常不是正确的 2-3 树。
我的一个想法是构建完美平衡的 BST，然后尝试将键从最后一个不完整的层向上移动。但这只是一个模糊的描述，我认为这无论如何都会导致线性复杂性。
知道 ab 树不是快速合并的好选择，但我认为在线性时间内应该是可能的。