加入两棵红黑树的最佳方式

Question

最简单的方法是将两个树存储在两个数组中，合并它们并构建一个新的红黑树，其中排序的数组需要O（m + n）次。

是否有一个时间复杂度较低的算法？

Answer 1

您可以在时间O（m log（n / m + 1））中合并两个红黑树，其中n和m是输入大小，WLOG，m≤n。请注意，此边界比O（m + n）更紧密。这是一些直觉：

• 当两棵树的大小相似（m≈n）时，界限约为O（m）= O（n）= O（n + m）。
• 当一棵树明显大于另一棵树（m << n）时，边界约为O（log n）。

你可以找到算法here的简短描述。可以在recent paper中找到更广泛的描述，其推广到其他平衡方案（AVL，BB [α]，Treap，......）。

Answer 2

由于你需要比较element和m n中的每个Red-Black Trees这一事实，你将不得不处理O(m+n)时间复杂度的最小值，有一种方法可以做到O(1)空间复杂度，但这是其他什么都没有你的问题。如果你没有迭代并检查每个element中的每个Red-Black Tree，你不能保证你的新Red-Black Tree将被排序。我可以想到另一种合并两个Red-Black Trees的方式，它称为“使用DLL的就地合并”，但是这个也会导致O(m+n)时间复杂度。

1. 将给定的两个Red-Black Trees转换为Doubly Linked List，其具有O(m+n)时间复杂度。
2. 合并两个排序的Linked Lists，它具有O(m+n)时间复杂度。
3. 从步骤2中创建的合并的Red-Black Tree构建平衡的list，其具有O(m+n)时间复杂度。

这种方法的时间复杂性也是O(m+n)。

因此，由于您必须将每个树的元素与另一个树的其他元素进行比较，因此您必须至少使用O(m+n)。