二叉樹 - 斯卡拉遞歸的樹木

Question

這裏的工會是二叉樹的實現，我在Coursera，3周馬丁·奧德斯基的視頻講座看到：

abstract class IntSet 
{ 
    def incl(x: Int): IntSet 
    def contains(x: Int): Boolean 
    def union(other: IntSet): IntSet 
} 

object Empty extends IntSet 
{ 
    def contains(x: Int): Boolean = false 
    def incl(x: Int): IntSet = new NonEmpty(x, Empty, Empty) 
    def union(other: IntSet): IntSet = other 

    override def toString = "." 
} 

class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet 
{ 
    def contains(x: Int): Boolean = 
    if (x<elem) left contains x 
    else if (x > elem) right contains x 
    else true 

    def incl(x: Int): IntSet = 
    if (x<elem) new NonEmpty(elem, left incl x, right) 
    else if (x > elem) new NonEmpty(elem, left, right incl x) 
    else this 

    def union(other: IntSet): IntSet = 
    ((left union right) union other) incl elem 

    override def toString = "{" + left + elem + right + "}" 
} 

如此空虛和非空遵循的標準概述由IntSet。我感興趣的是NonEmpty類中的聯合方法。我想了解它是如何工作的。

我做了下面一個小的描述來解釋我的思考過程：

對我來說，看起來好像有一個無限循環出現。但我比某些更把我所造的下方某處的評估錯誤：

1. （（L_1üR_1）UO），包括E1
2. （（L_3üR_3）U R_1），包括E3
3. （歐盟R_1），包括E3
4. 2.
5. 3.
6. 2. 等 等

Answer 1

讓我們來看看我是否可以用你的圖解析出來。

((left union right) union other) incl elem變爲：((L1 u R1) u OE1) incl 5

展開內部括號：((L2 u R2) u R1) incl 3

L2和R2都是空的，所以這樣會合攏到：R1 incl 3，這是一個新NonEmpty，是不是你的圖所示。

插入原來的公式是：((R1 incl 3) u OE1) incl 5

這是越來越難來圖，但是，你可以看到，我們已經刪除L1從計算並用新的，稍微大一點，NonEmpty取代R1。以這種方式繼續下去，所有東西都會減少到一個新的IntSet，其中包括前一個的所有值。