英文:
Counterexample for binary search trees can be always joined in logarithmic time
问题
问题是，基本上，有没有两个平衡的二叉搜索树的示例，无法在对数时间内合并？
动机：
假设我们有两个平衡的二叉搜索树T1和T2，分别具有n和m个节点。它们的深度是对数的（分别为O(log n)和O(log m)）。假设n <= m。
如果T1和T2的值区间不重叠，即max T1 < min T2（或max T2 < min T1），那么如果我们使用例如Splay树或Treaps，合并这些树可以非常高效（O(log m))。
否则，我所知道的最好算法是一个线性的O(n + m)算法（遍历两棵树，然后合并值并创建一个新的平衡树）。
这远不如对数，但（在四处涂鸦时）我无法找到需要使用此算法的大小为n的两棵树（对于某个任意大的n）。
英文:
The question is, basically, what would be an example of two balanced binary search trees that cannot be merged in logarithmic time?
Motivation:
Suppose we have two balanced binary search trees T1 and T2 with n and m nodes respectively. Their depth is logarithmic (O(log n) and O(log m) respectively). Suppose n <= m.
If the intervals of values of T1 and T2 do not overlap, i.e., max T1 < min T2 (or max T2 < min T1), joining those trees can be really efficient (O(log m)) if we use, e.g., Splay trees or Treaps.
Otherwise, the best algorithm I am aware of is a linear O(n + m) algorithm (inorder traversal of both trees followed by merging the values and the creation of a new balanced tree).
This is much worse than logarithmic but (while doodling around) I could not find two trees of size n (for some arbitrary large n) where it would be necessary to use this algorithm.
答案1
得分: 1
构建一个长度为 m 的平衡二叉树，包括范围 2..2m 中的偶数。再构建一个长度为 m 的平衡二叉树，包括范围 1..2m-1 中的奇数。
合并后的二叉树需要包含 O(m) 个节点，其中节点的值来自一个树，而子节点来自另一个树。因此，合并操作至少需要构建 O(m) 个新节点，耗时 O(m)。
英文:
Make one a balanced binary tree of length m of the even numbers in the range 2..2m. Make the other a balanced binary tree of length m of the odd numbers in the range 1..2m-1.
The merged binary tree needs to wind up with O(m) nodes with values from the one tree with children are from the other tree. And therefore you cannot merge without constructing at least O(m) new nodes, which takes O(m) time.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论