如何有效地合并两个 BST？-algorithm-IT问答社区-解决你的IT疑问

如何有效地合并两个 BST？

dimmg 1月前

如何合并两个二叉搜索树并保持 BST 的属性？如果我们决定从一棵树中取出每个元素并将其插入到另一棵树中，则此方法的复杂度将为 O(n1 * log(...

如何合并两棵二叉搜索树并保持 BST 的属性？

如果我们决定从一棵树中取出每个元素并将其插入到另一棵树中，则此方法的复杂度将是 O(n1 * log(n2)) ， n1 其中是已拆分的 T1 树（假设）的节点数 n2 是另一棵树（假设）的节点数 T2 。经过此操作后，只有一个 BST 有 n1 + n2 节点。

我的问题是：我们能做得比 O(n1 * log(n2)) 更好吗？

帖子版权声明 1、本帖标题：如何有效地合并两个 BST？
本站网址：http://xjnalaquan.com/
2、本网站的资源部分来源于网络，如有侵权，请联系站长进行删除处理。
3、会员发帖仅代表会员个人观点，并不代表本站赞同其观点和对其真实性负责。
4、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
5、站长邮箱：yeweds@126.com 除非注明，本帖由dimmg在本站《algorithm》版块原创发布，转载请注明出处！

最新回复 (0)

最新倒序只看楼主

Ngoc Nam 1月前 0 取消查看

引用 4楼
Naaff 的回答更详细一些：
- 将 BST 展平为排序列表需要 O(N)
  - It's just "in-order" iteration on the whole tree.
  - Doing it for both is O(n1+n2)
- 将两个排序列表合并为一个排序列表的复杂度为 O(n1+n2)。
  - Keep pointers to the heads of both lists
  - Pick the smaller head and advance its pointer
  - This is how the merge of merge-sort works
- 从排序列表创建完美平衡的 BST 时间为 O(N)
  - See code snippet below for algorithm[1]
  - In our case the sorted list is of size n1+n2. so O(n1+n2)
  - The resulting tree would be the conceptual BST of binary searching the list
O(n1+n2) 的三个步骤导致 O(n1+n2)

对于同一数量级的 n1 和 n2，这比 O(n1 * log(n2)) 更好

[1] 从排序列表创建平衡 BST 的算法（Python 中）：
```
def create_balanced_search_tree(iterator, n):
    if n == 0:
        return None
    n_left = n//2
    n_right = n - 1 - n_left
    left = create_balanced_search_tree(iterator, n_left)
    node = iterator.next()
    right = create_balanced_search_tree(iterator, n_right)
    return {'left': left, 'node': node, 'right': right}
```