2

好的，我已经binary search tree在 OCaml 中编写了一个。

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 将不会包含上一个树中的完整节点，对吗？

那么我应该如何在 OCaml 中编写一个 bst，以便我们使用前一棵树的所有节点创建一个新的 bst，以保持前一棵树不可变？如果每次我需要从旧 bst 复制所有节点，那会影响性能吗？

编辑：

所以我们一开始就说，一个 bst 是用一个 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 中的两个(5, Leaf, Leaf)s 完全一样吗？

4

2 回答 2

5

我将尝试回答您问题的共享部分。简短的回答是肯定的，两棵树的两个部分将是相同的。不可变数据之所以如此有效，是因为对可能的共享没有限制。这就是为什么 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

长答案是不能保证这两个部分是相同的。如果编译器和/或运行时可以看到复制子树的原因，那么它也可以自由地这样做。在某些情况下（如分布式处理），这将是更好的选择。再次，关于 FP 的伟大之处在于对共享没有限制，这意味着在这种情况下，共享既不是必需的，也不是禁止的。

于 2013-01-22T16:16:15.283 回答
2

查看已接受的链接问题的答案。在此具体说明这一行：

让 tree_of_list l = List.fold_right 插入 l 叶

找出正在发生的事情的链条。以列表 1、2、3 为例。

首先我们没有树和插入 1 叶的结果。

叫这个 T1

接下来是insert 2 T1生成的树

叫这个 T2

然后插入 3 T2 生成的树

这是作为 Tree_of_list 的结果返回的内容。

如果我们调用结果 T3，然后在代码中的其他地方调用 insert 4 T3，则从 insert 返回的结果与使用列表 1、2、3、4 调用 Tree_of_list 没有区别。

于 2013-01-22T15:23:36.803 回答