functional-programming - 在 OCaml 中构建二叉搜索树的正确方法

Question

好的，我已经用 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

---

上面的代码据说在The right way to use a data structure in 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 是用一个节点 t1 = (10, Leaf, Leaf) 创建的。

然后我执行 let t2 = insert 5 t1，然后我得到 t2 = (10, (5, Leaf, Leaf), Leaf)，对吗？在 t2 中，让我们给子节点 (5, Leaf, Leaf) 一个变量 c1

然后我执行 let t5 = insert 12 t2，然后我得到 t3 = (10, (5, Leaf, Leaf), (15, Leaf, Leaf))。让我们给子节点 (5, Leaf, Leaf) 一个变量 c2

所以我的问题是是否c1 == c2？ t2和t3中的两个(5, Leaf, Leaf)是否完全一样？

Answer 1

我将尝试回答您问题的共享部分。简短的回答是肯定的，两棵树的两个部分将是相同的。不可变数据之所以如此有效，是因为对可能的共享没有限制。这就是 FP 运作良好的原因。

这是一个执行您描述的 session :

# 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 的优点在于对共享没有限制，这意味着在这种情况下既不需要也不禁止共享。