我正在上Scala的课程，我不明白两个函数之间的效率差异。这门课程是关于二叉搜索树的，它包含被描述为TweetSets的tweet，特别是union函数，让我感到困惑。
我知道第一个方法分解了树，并通过incl函数将元素添加到树中，但我不明白为什么第二个方法更好。
一棵树可以描述为：

class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet:

字符串
这是两个联合函数：

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

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

的数据
它们都终止于空集合中的函数并集：

def union(that: TweetSet): TweetSet = that

型
我知道第二个函数更有效，因为它通过了测试，而第一个没有。
编辑：我应该添加一些代码来进一步解释类。我将在下面通过它们。
这是空集：

class Empty extends TweetSet:

  def union(that: TweetSet): TweetSet = that
  def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = acc

  def mostRetweeted: Tweet = throw java.util.NoSuchElementException()
  def helper(most: Tweet) = most

  def descendingByRetweet: TweetList = Nil

  /**
   * The following methods are already implemented
   */

  def contains(tweet: Tweet): Boolean = false

  def incl(tweet: Tweet): TweetSet = NonEmpty(tweet, Empty(), Empty())

  def remove(tweet: Tweet): TweetSet = this

  def foreach(f: Tweet => Unit): Unit = ()

型
这就是非空：

class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet:

  def union(that: TweetSet): TweetSet = left.union(right.union(that).incl(elem))
  def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet =
    if p(this.elem) then left.union(right).filterAcc(p, acc.incl(this.elem))
    else left.union(right).filterAcc(p, acc)

  def mostRetweeted: Tweet = helper(this.elem)
  
  def helper(most: Tweet): Tweet = 
    if this.elem.retweets > most.retweets then left.union(right).helper(elem)
    else left.union(right).helper(most)

  
  def descendingByRetweet: TweetList = Cons(this.mostRetweeted, this.remove(this.mostRetweeted).descendingByRetweet)

  /**
   * The following methods are already implemented
   */

  def contains(x: Tweet): Boolean =
    if x.text < elem.text then
      left.contains(x)
    else if elem.text < x.text then
      right.contains(x)
    else true

  def incl(x: Tweet): TweetSet =
    if x.text < elem.text then
      NonEmpty(elem, left.incl(x), right)
    else if elem.text < x.text then
      NonEmpty(elem, left, right.incl(x))
    else
      this

  def remove(tw: Tweet): TweetSet =
    if tw.text < elem.text then
      NonEmpty(elem, left.remove(tw), right)
    else if elem.text < tw.text then
      NonEmpty(elem, left, right.remove(tw))
    else
      left.union(right)

  def foreach(f: Tweet => Unit): Unit =
    f(elem)
    left.foreach(f)
    right.foreach(f)

型
至于测试，第一个实现没有完成，因为它花了很长时间。我在开始时发布的第二个联盟方法立即完成。