scala - 二叉树 - 用于树并集的 Scala 递归

Question

以下是我在第 3 周 Martin Odersky 在 Coursera 上的视频讲座中看到的二叉树的实现:

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 + "}"
}

因此 Empty 和 NonEmpty 遵循 IntSet 概述的标准。我感兴趣的是 NonEmpty 类中的 union 方法。我想了解它是如何工作的。

我在下面做了一个小描述来解释我的思考过程:


对我来说，似乎那里有一个无限循环。但我非常确定我在下面的某个地方犯了一个评估错误:

((L_1 U R_1) U O) 包括 1

((L_3 U R_3) U R_1) 包括 3

(E U R_1) 包括 e3

2.

3.

2.
等等。
等

Answer 1

让我们看看我是否可以使用您的图表解析它。
((left union right) union other) incl elem变成:((L1 u R1) u OE1) incl 5
将内括号展开为:((L2 u R2) u R1) incl 3L2和 R2都是空的，所以这会折叠为:R1 incl 3 ，这是一个新的 NonEmpty那不在你的图表中。

将此代入原始公式:((R1 incl 3) u OE1) incl 5
这越来越难以绘制，但正如您所见，我们已删除 L1从计算和替换 R1一个新的，稍大一点，NonEmpty .以这种方式继续，一切都会减少到一个新的 IntSet这包括以前的所有值。