如何有效地合并两个BST？
如何合并两个保持BST属性的二叉搜索树？
如果我们决定从一棵树中取出每个元素并将其插入到另一个元素中，则此方法的复杂度将为O(n1 * log(n2))，其中n1是T1我们已拆分的树的节点数（例如），n2是的结点数。另一棵树（例如T2）。此操作后，只有一个BST具有n1 + n2节点。
我的问题是：我们能做得比O（n1 * log（n2））好吗？
问题答案：
纳夫的答案还有更多细节：
- 将BST展平为排序列表为O（N）
- 它只是整个树上的“有序”迭代。
- 两者都做O（n1 + n2）
- 将两个已排序列表合并为一个已排序列表是O（n1 + n2）。
- 保持指针指向两个列表的开头
- 选择较小的头部并前进其指针
- 这是合并排序合并的工作方式
- 从排序列表中创建一个完美平衡的BST是O（N）
- 有关算法，请参见下面的代码片段[1]
- 在我们的情况下，排序列表的大小为n1 + n2。所以O（n1 + n2）
- 结果树将是二进制搜索列表的概念性BST。
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}
-
问题内容： 我有两个键为s且值为的映射。给定两个s，合并它们的最简单方法是什么，如果两个键相同，则值是两个集合的并集。您可以假设值永远不会为null，并且如果有用的话，我们可以将它们设为s。 问题答案： 我们在谈论实例。在这种情况下，查找值为O（1），因此您只需获取一个映射，然后对该映射的条目进行迭代，看看另一个映射是否包含该键。如果没有，只需添加设置。如果包含密钥，则将两个集合并集（通过将一个集
-
问题内容： 我有第一个json： 第二个： 我想合并/合并两个数据数组，例如： （我现在不在乎）。 如何快速简便地做到这一点？这是我的尝试： 但是会引发异常： 问题答案： JArray dataOfJson1=json1.SelectToken(“data”);
-
问题内容： 我有两个文件（ file1.txt 和 file2.txt ），这些文件仅是示例。 如何合并两个文件，以创建文件 -merge_files.txt 作为示例3 我现在写ksh脚本，所以可以用ksh，awk，sed，perl一个内衬… etc合并 背景-为什么我需要合并文件： 我的目标是将 OLD文件 （存在于第一个字段中）重命名为 NEW文件 （存在于第二个字段中）， 例子1 例子2
-
问题内容： 如何合并结构相同的两个MySQL表？ 这两个表的主键将发生冲突，因此我考虑了这一点。 问题答案： 您也可以尝试： 这允许table_1中的行取代table_2中具有匹配主键的行，同时仍插入具有新主键的行。 或者， 将使用来自表_2的相应行更新表_1中已经存在的行，同时插入具有新主键的行。
-
问题内容： 我有以下代码，该代码分析YAML文件，并且需要匹配一个结构的值并更新该结构的属性。 例如，这是yaml文件（为简单起见翻译为bin）和正确解析的内容 最后，我需要做的是将内部yaml文件更改为上面的结构 。更改是 当我需要 修改 的值时，这里是从to 和to 问题在于第二个循环，我应该使用它来迭代和匹配的值，我不确定如何以有效的方式将它们组合在一起。 问题答案： Golang常见问题解
-
我有两个xml文件，需要将它们合并为一个xml。以下是示例： orginal.xml文件： 使现代化xml文件： 它们应合并为如下xml文件： 实际上，我想使用更新。xml来更新原始。xml： > update.xml中的新员工应该被添加到original.xml 在更新中修改了员工信息。xml应覆盖相应的员工节点。 我对XSLT略知一二，但我的知识还不足以找出适合合并的XSLT。