11

scala でカスタム オブジェクトのツリーを作成していますが、末尾再帰ではないため、insert メソッドがスタック オーバーフローをスローします。ただし、末尾再帰にする方法がよくわかりません。関連する例で「アキュムレータ」変数を使用しているのを見てきましたが、それらは単純に乗算して上書きできる整数のようなものか、ツリーに適応するのに苦労しているリストのいずれかでした。ここに私が持っているものがあります:

私の木の基礎:

abstract class GeoTree
case object EmptyTree extends GeoTree
case class Node(elem:GeoNode, left:GeoTree, right:GeoTree) extends GeoTree

ツリーを再帰的に作成する挿入メソッド (スタック オーバーフローを引き起こすメソッド):

  def insert(t:GeoTree, v: GeoNode): GeoTree = t match {
    case EmptyTree => new Node(v, EmptyTree, EmptyTree)
    case Node(elem:GeoNode, left:GeoTree, right:GeoTree) => {
      if (v < elem) new Node(elem, insert(left, v), right)
      else new Node(elem, left, insert(right, v))
    }
  }

GeoNodeのコードは非常に単純なので、実際には特に関連性があるとは思いません。このクラスには 2 つのLong属性と、ツリー内で使用するために適切にオーバーライドされた<>、および演算子があります。==私のinsert関数にアキュムレータを使用する方法、または末尾再帰にする他の方法について誰かが提案できますか?

4

1 に答える 1

16

関数を末尾再帰にすることはできません。その理由は、 への再帰呼び出しがinsert計算を終了しないためです。これらは部分式として使用されます。この場合はnew Node(...). 例えば。一番下の要素を探しているだけなら、簡単に末尾再帰にすることができます。

何が起こっているか: ツリーを下に降りてinsert各ノードを呼び出しますが、一番下の葉を新しい値に置き換えた後にツリーを再構築する必要があるため、ルートに戻る方法を覚えておく必要があります。

考えられる解決策:スタック上ではなく、ダウン パスを明示的に覚えておいてください。例として単純化されたデータ構造を使用してみましょう。

sealed trait Tree;
case object EmptyTree extends Tree;
case class Node(elem: Int, left:Tree, right:Tree) extends Tree;

次に、パスとは何かを定義します。これは、右または左に移動した場合の情報を含むノードのリストです。ルートは常にリストの最後にあり、葉は最初にあります。

type Path = List[(Node, Boolean)]

これで、値を指定してパスを計算する末尾再帰関数を作成できます。

// Find a path down the tree that leads to the leaf where `v` would belong.
private def path(tree: Tree, v: Int): Path = {
  @tailrec
  def loop(t: Tree, p: Path): Path =
    t match {
      case EmptyTree        => p
      case n@Node(w, l, r)  =>
        if (v < w) loop(l, (n, false) :: p)
        else       loop(r, (n, true)  :: p)
    }

  loop(tree, Nil)
}

パスと値を取り、パスの下部にある新しいノードとして値を持つ新しいツリーを再構築する関数:

// Given a path reconstruct a new tree with `v` inserted at the bottom
// of the path.
private def rebuild(path: Path, v: Int): Tree = {
  @tailrec
  def loop(p: Path, subtree: Tree): Tree =
    p match {
      case Nil                          => subtree
      case (Node(w, l, r), false) :: q  => loop(q, Node(w, subtree, r))
      case (Node(w, l, r), true)  :: q  => loop(q, Node(w, l, subtree))
    }
  loop(path, Node(v, EmptyTree, EmptyTree))
}

挿入は簡単です:

def insert(tree: Tree, v: Int): Tree =
  rebuild(path(tree, v), v)

このバージョンは特に効率的ではないことに注意してください。Seqおそらく、 を使用するか、変更可能なスタックを使用してパスを保存することで、より効率的にすることができます。しかしList、アイデアをうまく​​表現することができます。

免責事項:私はコードをコンパイルしただけで、まったくテストしていません。

ノート:

  • これは、ジッパーを使用して関数ツリーをトラバースする特別な例です。ジッパーを使用すると、同じアイデアをあらゆる種類の木に適用して、さまざまな方向に木を歩くことができます。
  • ツリーを要素のより大きなセットに役立つようにしたい場合 (スタック オーバーフローが発生している場合は、おそらくそうするでしょう)、それをself-balancedにすることを強くお勧めします。つまり、深さが常にO(log n)になるようにツリーの構造を更新します。そうすれば、すべての場合で操作が高速になり、スタック オーバーフローを心配する必要がなくなり、スタックベースの非末尾再帰バージョンを使用できます。おそらく自己均衡ツリーの最も簡単な変形はAA ツリーです。
于 2013-07-07T13:01:27.987 に答える