関数を末尾再帰にすることはできません。その理由は、 への再帰呼び出しが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 ツリーです。