Scala 二叉搜索树的并集运算

Question

我是 Scala 新手，我一直无法理解以下代码 from this link 的作用。适用于二叉搜索树:

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

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

我不明白的是，联合操作如何按排序顺序创建新树以及它到底是如何工作的，它是否会到达树的末尾，然后一一添加元素？另外，我不明白这个递归如何终止，就 Java 而言，它可能应该给我们 NullPointerException

Answer 1

总结算法的工作原理(因为问题中只有一部分，终止在 Empty 情况下):

要合并两个 TweetSet，请查看左侧:

• 如果它是空的，则联合应该是另一个，所以Empty union that == that

• 如果它非空，那么它有一个根元素elem，一个left子树和一个right子树。然后，由 left、right、that 中的所有元素以及元素 elem 形成并集，所以我们对所有这些递归调用union。

在最后一种情况下，为了确保我们能够终止，每个 union 调用中的左侧元素应该小于初始调用(否则，我们将陷入递归循环，其中union 的左侧会越来越大)。表达式

left union (right union that)

正是这样做的:

• right 小于初始 NonEmpty(elem, left, right) (作为其右子树)，因此 右并集 最终会被计算

• left 也比初始树小，因此 left union (...) 最终也会被计算。

然后我们添加最终缺失的元素elem来构建最终的TweetSet。请注意，如果您尝试将此算法应用于小集合，它将返回到将第一个集合的所有元素逐个添加到第二个集合，从最大的元素开始(初始树中右侧最远的元素) 。特别是，第二组的大小不影响算法的长度。