Scala中两种TweetSet递归union函数的效率差异疑惑

先明确两种union实现的核心代码：

第一种实现（低效） #

def union(that: TweetSet): TweetSet = left.union(right).union(that).incl(elem)

第二种实现（高效） #

def union(that: TweetSet): TweetSet = left.union(right.union(that).incl(elem))

两者依赖的Empty类union终止条件一致：

def union(that: TweetSet): TweetSet = that

效率差异的核心原因：递归顺序与插入时机 #

两种实现的本质区别在于合并操作的顺序和当前节点elem插入的时机，这直接影响了incl（二叉搜索树插入）操作的时间复杂度：

1. 第一种实现的执行流程与复杂度 #

对于NonEmpty(elem, L, R)节点，第一种实现的步骤是：

1. 先合并左子树L和右子树R，得到包含L+R所有节点的树LR
2. 再将LR与that合并，得到包含L+R+that所有节点的树LRThat
3. 最后把当前节点的elem插入到LRThat中

问题出在第三步：每次插入elem时，目标树LRThat已经包含了当前节点的所有子孙节点和that的节点。随着递归深入，目标树规模快速膨胀，而incl的时间复杂度取决于树的高度——若递归生成的树不平衡（比如链表状结构），incl的时间会从O(log n)退化为O(n)。

整体时间复杂度为O(n²)，数据量较大时会直接导致超时。

2. 第二种实现的执行流程与复杂度 #

同样针对NonEmpty(elem, L, R)节点，第二种实现的步骤是：

1. 先合并右子树R与that，得到包含R+that所有节点的树RThat
2. 把当前节点的elem插入到RThat中，得到RThatElem
3. 最后将左子树L与RThatElem合并

这里的关键是：elem插入的目标树是RThat（仅R+that的大小），而非第一种实现中包含所有子孙节点的大集合。递归过程中每次合并的都是规模更小的子树，incl操作的时间复杂度能稳定保持在O(log n)级别。

整体时间复杂度为O(n log n)，数据量较大时依然能高效执行，这也是测试中它能快速完成的原因。

直观对比：链状树的极端情况 #

假设我们有一个n个节点的链状TweetSet（每个节点的right为空，left指向子节点）：

• 第一种实现会每次将前面所有节点合并后的树与that合并，再插入当前节点，总插入时间为1+2+...+n = O(n²)
• 第二种实现会将每个节点逐个插入到that的合并结果中，再交给左子树合并，总插入时间为n*O(log n) = O(n log n)

这种极端场景下的差异最明显，也直接解释了测试中的超时现象。

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