OCaml中构建二叉搜索树的正确方法

Question

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

---

上面的代码在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 中，我们给一个变量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是否完全相同？

Answer 1

我将尝试回答您问题的共享部分。简短的回答是肯定的，两棵树的两个部分将是相同的。不可变数据之所以如此有效，是因为它对可能的共享没有任何限制。这就是 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 的伟大之处在于，对共享没有限制，这意味着在这种情况下既不需要也不禁止共享。