CODEWITHSUNDEEP
scala
naz
naz

Reputation: 2072

Binary Trees - 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: enter image description here

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:

  1. ((L_1 U R_1) U O) incl e1
  2. ((L_3 U R_3) U R_1) incl e3
  3. (E U R_1) incl e3
  4. 2.
  5. 3.
  6. 2. etc. etc.

Upvotes: 4

Views: 403

Answers (1)

jwvh
jwvh

Reputation: 51271

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.

Upvotes: 3

Related Questions