寻求无法在对数时间内合并的两棵平衡二叉搜索树实例

核心问题 #

寻找无法在对数时间内完成合并的两棵平衡二叉搜索树实例。

背景设定 #

给定两棵平衡二叉搜索树T₁和T₂：

• T₁包含n个节点，深度为O(log n)；T₂包含m个节点，深度为O(log m)，且满足n ≤ m
• 两棵树均为平衡结构，深度处于对数级别

已知高效合并场景 #

当T₁和T₂的取值区间完全不重叠时（即max(T₁) < min(T₂) 或 max(T₂) < min(T₁)），使用伸展树（Splay Tree）或树堆（Treap）这类数据结构，能在**O(log m)**的对数时间内完成高效合并。

区间重叠时的现状 #

如果两棵树的取值区间存在重叠，目前已知的最优合并算法是线性时间复杂度O(n+m)：

1. 分别对T₁和T₂做中序遍历，得到两个有序序列
2. 合并这两个有序序列后，重新构建一棵新的平衡二叉搜索树

这种线性算法的效率远低于对数时间，但目前尚未找到任意大n规模下，必须使用该线性算法的两棵树实例——也就是说，既没有确凿的反例证明这类场景下不存在对数时间合并方法，也没有算法能实现对数时间合并。

内容的提问来源于stack exchange，提问作者Antoine