Scala Recursion for the union of trees

Here is the implementation of binary trees that I have seen in Martin Odersky's video lectures on Coursera, week 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 + "}"
}

So Empty and NonEmpty follow the standards outlined by the IntSet. What I am interested in, is the union method in the NonEmpty class. I would like to understand how it works.

I have made a small depiction below to explain my thinking process:

To me it appears as if there is an infinite loop there. But I am more than certain that I have made an evaluation mistake somewhere below:

((L_1 U R_1) UO) incl e1

((L_3 U R_3) U R_1) incl e3

(EU R_1) incl e3

2.

3.

2. etc. etc.

---

Let's see if I can parse this out using your diagram.

((left union right) union other) incl elem becomes: ((L1 u R1) u OE1) incl 5

Expand the inner parentheses to: ((L2 u R2) u R1) incl 3

L2 and R2 are both empty so this collapses to: R1 incl 3 , which is a new NonEmpty that isn't in your diagram.

Plug this into the original formula: ((R1 incl 3) u OE1) incl 5

This is getting harder to diagram but, as you can see, we've removed L1 from the calculations and replaced R1 with a new, slightly larger, NonEmpty . Continuing in this manner everything will be reduced to a new IntSet that includes all the values from the previous.

链接地址: http://www.djcxy.com/p/62790.html

上一篇: Android Jar库

下一篇: 斯卡拉递归树的联合