2

binary search treeOK、 OCaml でa を書きました。

type 'a bstree = 
    |Node of 'a * 'a bstree * 'a bstree
    |Leaf


let rec insert x = function
    |Leaf -> Node (x, Leaf, Leaf)
    |Node (y, left, right) as node -> 
        if x < y then
            Node (y, insert x left, right)
        else if x > y then
            Node (y, left, insert x right)
        else
            node

上記のコードは、OCaml でデータ構造を使用する正しい方法で優れていると言われていました。

しかし、問題が見つかりました。これinsertは、次のように、リストから bst を一度に作成する場合にのみ機能します。

let rec set_of_list = function
     [] > empty
   | x :: l > insert x (set_of_list l);;

したがって、リストから連続して bst を作成しても問題ありません。リストからすべてのノードを含む完全な bst を取得できます。

ただし、以前にビルドした bst があり、ノードを挿入したい場合、結果の bst には以前のツリーからの完全なノードが含まれません。よろしいですか?

では、以前のツリーを不変に保つために、以前のツリーのすべてのノードで新しい bst を作成するには、OCaml で bst をどのように記述すればよいでしょうか? 毎回古い bst からすべてのノードをコピーする必要がある場合、パフォーマンスに影響はありますか?

編集：

最初に、bst が 1 つの node で作成されるとしましょうt1 = (10, Leaf, Leaf)。

それから私はそうしますlet t2 = insert 5 t1、そして私は得t2 = (10, (5, Leaf, Leaf), Leaf)ますよね？t2 の中で、変数を与えましょうc1 to the child node (5, Leaf, Leaf)

それから私はそうしますlet t5 = insert 12 t2、そして私は得t3 = (10, (5, Leaf, Leaf), (15, Leaf, Leaf))ます。変数を与えましょうc2 to the child node (5, Leaf, Leaf)

だから私の質問はc1 == c2？t2 と t3の 2 つ(5, Leaf, Leaf)の はまったく同じですか?

4

2 に答える 2

5

あなたの質問の共有部分に答えようとします。短い答えはイエスです。2 つのツリーの 2 つの部分は同一になります。不変データがうまく機能する理由は、可能な共有に制限がないからです。FPがうまく機能するのはそのためです。

あなたが説明したことを行うセッションは次のとおりです。

# let t1 = Node (10, Leaf, Leaf);;
val t1 : int bstree = Node (10, Leaf, Leaf)
# let t2 = insert 5 t1;;
val t2 : int bstree = Node (10, Node (5, Leaf, Leaf), Leaf)
# let t3 = insert 12 t2;;
val t3 : int bstree = Node (10, Node (5, Leaf, Leaf), Node (12, Leaf, Leaf))
# let Node (_, c1, _) = t2;;
val c1 : int bstree = Node (5, Leaf, Leaf)
# let Node (_, c2, _) = t3;;
val c2 : int bstree = Node (5, Leaf, Leaf)
# c1 == c2;;
- : bool = true

長い答えは、2 つの部分が同一であるという保証はないということです。コンパイラーおよび/またはランタイムがサブツリーをコピーする理由を認識できる場合、それも自由に行うことができます。(分散処理のように) それがより良い選択になる場合があります。繰り返しになりますが、FP の優れた点は、共有に制限がないことです。つまり、そのような場合に共有が要求されたり、禁止されたりすることはありません。

于 2013-01-22T16:16:15.283 に答える
2

リンクされた質問に対する受け入れられた回答を見てください。ここでこの行を特定するには：

let tree_of_list l = List.fold_right insert l 葉

何が起こっているかの連鎖を解決します。リスト 1,2,3 を取ります。

まず、ツリーがなく、1 リーフを挿入した結果が得られます。

これを T1 と呼ぶ

次は、insert 2 T1 によって生成されたツリーです。

これをT2と呼ぶ

次に、挿入 3 T2 によって生成されたツリー

これが Tree_of_list の結果として返されるものです。

結果を T3 と呼ぶと、コード call insert 4 T3 のどこかで、リスト 1,2,3,4 で Tree_of_list を呼び出す場合と、insert から返される結果に違いはありません。

于 2013-01-22T15:23:36.803 に答える