最简单的方法是将两棵树存储在两个数组中，将它们合并并构建一个新的红黑树，该树的排序数组需要 O(m + n) 次。
有没有时间复杂度更小的算法？
最佳答案
您可以在 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 等)。 .
关于algorithm - 加入两棵红黑树的最佳方式，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43697546/