Hey. There is a code of a certain recursive union function in the NonEmpty class, which combines two binary search trees into one. It would be great if it was not difficult for anyone to explain in detail (preferably by example) how it works. For the best understanding I will add a class in which there is an interest to me.

 abstract class TweetSet { def union(that: TweetSet): TweetSet def incl(tweet: Tweet): TweetSet } class Empty extends TweetSet { override def union(that: TweetSet): TweetSet = that def incl(tweet: Tweet): TweetSet = new NonEmpty(tweet, new Empty, new Empty) } class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet { override 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 } }
  • one
    Hi, it seems to me that in this implementation there is an error: the union called on NonEmpty will descend recursively first to the right end of the tree, then when it reaches Empty, Empty.union will work: then it rises to a higher level and also executes with the left subtree: (right Empty.union that) -> that then (left NonEmpty.union that). Look at this implementation, maybe there is no error here: gist.github.com/rbaron/8ca634b2aee69b3262ff , where the NonEmpty.union method is implemented differently. incl applies to result (right union that) - Alexander du Sautoy

1 answer 1

When combining collections, 2 cases are possible: a union with an empty collection (it will give the 1st collection) and a non-empty one.

To explain the merging process with a non-empty collection, consider the incl (x: Tweet) method. Each of its calls recursively rearranges the left or right subtree, depending on the argument.

The union method (that: TweetSet) recursively merges one of the subtrees of the current tree with the tree that, then the other subtree also merges with the result, and finally adds a root to the resulting tree.

For clarification by example, you can add methods to visualize the result.

 class Tweet(val text: String) class Empty extends TweetSet { .... override def toString = "." } class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet { override def union(that: TweetSet): TweetSet = { val res = (left union (right union that)).incl(elem) println(s"union ${this} and ${that} is " + res) res } ... override def toString = "{" + left + "," + right + "}" }

Next, the test code itself:

 object ts { val emp = new Empty //> emp : Empty = . def generTweet = new Tweet(scala.util.Random.nextString(10)) //> generTweet: => Tweet def generTweets(n: Int) = for (i <- 0 until n) yield generTweet //> generTweets: (n: Int)scala.collection.immutable.IndexedSeq[Tweet] def generTweetSet(n: Int, acc: TweetSet = new Empty): TweetSet = if (n == 0) acc else generTweetSet(n-1, acc.incl(generTweet)) //> generTweetSet: (n: Int, acc: TweetSet)TweetSet val nonEmpty1 = generTweetSet(1) //> nonEmpty1 : TweetSet = {.,.} val nonEmpty2 = generTweetSet(1) //> nonEmpty2 : TweetSet = {.,.} nonEmpty1 union nonEmpty2 //> union {.,.} and {.,.} is {.,{.,.}} //| res0: TweetSet = {.,{.,.}} val nonEmpty3 = generTweetSet(2) //> nonEmpty3 : TweetSet = {{.,.},.} nonEmpty1 union nonEmpty3 //> union {.,.} and {{.,.},.} is {{.,.},{.,.}} //| res1: TweetSet = {{.,.},{.,.}} nonEmpty3 union nonEmpty1 //> union {.,.} and {.,.} is {{.,.},.} //| union {{.,.},.} and {.,.} is {{.,{.,.}},.} //| res2: TweetSet = {{.,{.,.}},.} val nonEmpty4 = generTweetSet(2) //> nonEmpty4 : TweetSet = {.,{.,.}} nonEmpty3 union nonEmpty4 //> union {.,.} and {.,{.,.}} is {.,{{.,.},.}} //| union {{.,.},.} and {.,{.,.}} is {.,{{.,{.,.}},.}} //| res3: TweetSet = {.,{{.,{.,.}},.}} }