1

2 つのバイナリ ツリーを (順序どおりに) 比較したいのですが、同じでない場合はできるだけ早く戻りたいと考えています。

両方のツリーをトラバースして出力を比較できることは知っていますが、よりスマートなソリューションが何らかの形で最も早い時期に返されることを望んでいます。

scala でエレガントな方法でこれを行うにはどうすればよいでしょうか? 俳優？

ノード：

case class Node(
  var data: Int,
  left:Option[Node],
  right:Option[Node]
)

私のメインには、現在まったく同じ3つのツリーがありますが、必要に応じて変更できるようにここに貼り付けるだけです:

def main( args:Array[String] ) = {
  val tree = Node( (3),
                       None,
                       Some(Node( (5),
                                  Some(Node( (1),
                                       None,
                                       None )),
                               Some(Node( (9),
                                        None,
                                        Some(Node( (15),
                                                   None,
                                                   None )) ))  ))  )

  val tree2 = Node( (3),
                      None,
                      Some(Node( (5),
                                 Some(Node( (1),
                                      None,
                                      None )),
                              Some(Node( (9),
                                       None,
                                       Some(Node( (15),
                                                  None,
                                                  None )) ))  ))  )
  val tree3 = Node( (3),
                      None,
                      Some(Node( (5),
                                 Some(Node( (1),
                                      None,
                                      None )),
                              Some(Node( (9),
                                       None,
                                       Some(Node( (15),
                                                  None,
                                                  None )) ))  ))  )
}
4

4 に答える 4

3

比較とトラバーサルの両方で短絡が必要な場合は、トラバーサルをStreamジェネレーターとしてキャストし、zip各トラバーサルからのストリームをforallorを使用existsして不一致を検出できます (forallそしてexists短絡し、すぐに停止します結果はわかっている）。

私はコードを書く時間がないので、もっと勤勉な人が書いてくれたら、チェックしてみてください!

于 2013-03-29T16:36:54.750 に答える
1

再帰を使用するだけです。ほぼ同一の巨大なツリーの場合を除いて、並列処理を使用しても何も得られないので、気にしないでください。何かのようなもの：

def same(n: Node, m: Node): Boolean = {
  if (n.data != m.data || 
      n.left.isEmpty != m.left.isEmpty || 
      n.right.isEmpty != m.right.isEmpty) {
    false
  }
  else if (n.left.exists(a => m.left.exists(b => !same(a,b)))) false
  else !n.right.exists(a => m.right.exists(b => !same(a,b)))
}

ツリーが数千レベルの深さになる可能性がある場合は、この適切な再帰戦略ではなく、幅優先の末尾再帰戦略に切り替える必要があります (深さ n で各側のすべての空でないノードを追跡することによって)。

于 2013-03-29T17:16:42.117 に答える
0 
object Main extends App {

  implicit val executor = ExecutionContext.global
  val branchLevel = 3

  def differentSequential(n1: Node, n2: Node) = differentOpt(Some(n1), Some(n2))

  def differentConcurrent(n1: Node, n2: Node) = differentPar(Some(n1), Some(n2), branchLevel)

  def differentOpt(n1: Option[Node], n2: Option[Node]): Boolean = {
    (n1, n2) match {
      case (Some(Node(d1, l1, r1)), Some(Node(d2, l2, r2))) =>
        d1 != d2 || differentOpt(l1, l2) || differentOpt(r1, r2)
      case _ => false
    }
  }

  def differentPar(n1: Option[Node], n2: Option[Node], level: Int): Future[Boolean] = {
    (n1, n2) match {
      case (Some(Node(d1, l1, r1)), Some(Node(d2, l2, r2))) => {
        if (d1 != d2)
          Future.successful(false)
        else if (level > 0) {
          val leftR = differentPar(l1, l2, level - 1)
          val rightR = differentPar(r1, r2, level - 1)
          combineOr(leftR, rightR)
        } else {
          Future.successful(differentOpt(l1, l2) || differentOpt(r1, r2))
        }
      }

      case _ => Future(false)
    }
  }

  private def combineOr(f1: Future[Boolean], f2: Future[Boolean]): Future[Boolean] = {
    val p = Promise[Boolean]()
    bind(p, f1, f2)
    bind(p, f2, f1)
    p.future
  }

  private def bind(p: Promise[Boolean], f: Future[Boolean], other: Future[Boolean]) {
    f.onComplete {
      case Success(x) => if (!x) p.completeWith(other) else p.trySuccess(true)
      case Failure(t) => p.tryFailure(t)
    }
  }


}

DifferentSequential は、可能な限り少数のノードを比較し、単純なパターン マッチングを使用します。ツリーの複数のブランチを同時にチェックし始めるバージョンも試しました。

注:このコードはテストされていません

于 2013-03-29T17:19:27.537 に答える