バイナリ木 - ここでは木

Question

の労働組合のためのScalaの再帰は週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クラスのunionメソッドです。私はそれがどのように機能するのか理解したいと思います。

私は私の思考プロセスを説明するには、以下の小さな描写を作っていますが、無限ループがあるかのように見える私に

を。税込E3

（（（L_1 U R_1）UO）税込E1

（（L_3 U R_3）U R_1）

1. ：しかし、私はどこか下の評価ミスを犯したことを一定以上にしていますEU R_1）税込E3
2. 2.
3. 3.
4. 2. など など

Answer 1

ダイアグラムを使ってこれを解析できるかどうかを見てみましょう。

((left union right) union other) incl elemは次のようになります。((L1 u R1) u OE1) incl 5

に内側の括弧を展開します。あなたの図にはない新しいNonEmptyある、R1 incl 3：((L2 u R2) u R1) incl 3

L2とR2は両方とも空になっているので、これはに崩壊します。元の式に

プラグこれは：((R1 incl 3) u OE1) incl 5

あなたが見ることができるように、これは、ダイアグラムに難しくなったがされ、我々は計算からL1削除され、新しい、わずかに大きい、NonEmptyでR1を交換しました。このように続けば、すべては前の値からすべての値を含む新しいIntSetに縮小されます。