斯卡拉工会操作

Question

我是新来的Scala和我被困与undestanding怎么下面的代码在二叉搜索树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方面它应该可能给我们空指针异常

Answer 1

总结算法是如何工作的（因为只有一部分是在问题中，终止在在Empty情况下）：

为了使两个TweetSet S上的工会，看左边的一个：

• 如果是空的，工会应当是其他人，所以Empty union that == that

• 如果它不是空的，则它具有根元素elem，left子树和right子树。然后由left，right,that和元素elem中的所有元素组成联合，因此我们在所有这些元素上递归调用union。

在最后这种情况下，以确保我们得到终止，在每个union调用左边元素应该比初始呼叫（否则，我们将陷入一个递归循环较小，其中左手union将会越来越大）。表达

left union (right union that) 

不正是：

• right比初始NonEmpty(elem, left, right)（即它的右子树）较小，所以right union that最终将被计算

• left也小于最初的树，所以left union (...)也将最终得到计算。

然后我们在最后加上缺少的元素elem生成最终TweetSet。请注意，如果您尝试将这个算法应用于小集合，则会返回将第一集合中的所有元素逐个添加到第二集合中，从最大的一个（最初的树中最右边的一个）开始， 。特别是，第二组的大小不影响算法的长度。