在OCaml中构建二进制搜索树的正确方法 [英] The correct way to build a Binary Search Tree in OCaml

问题描述

好的，我在OCaml中写了一个二元搜索树。

  type'a bstree = 
 |'a *'a bstree的节点*'a bstree 
 | Leaf 
 
 
让rec插入x =函数
 |叶 - >节点（x，叶，叶）
 |节点（y，左，右）作为节点 - > 
如果x < y然后
节点（y，插入x左，右）
 else if x> y然后
 Node（y，left，insert x right）
 else 
 node 
  

---

上面的代码据说在在OCaml中使用数据结构的正确方法

然而，我发现了一个问题。这个插入只有在一次构建一个bst的列表时才有效，比如

  let rec set_of_list = function 
 []>空
 | x :: l>插入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给子节点（5，Leaf，Leaf）

然后我做 let t5 = insert 12 t2 ，然后我得到 t3 =（10，（5，Leaf，Leaf），（15，Leaf，Leaf）） 。让我们给变量 c2给子节点（5，Leaf，Leaf）

所以我的问题是， code> c1 == c2 ？ t2和t3中的两个（5，Leaf，Leaf） s是否完全一样？

解决方案

查看关联问题的接受答案。
要具体说明这一行：

let tree_of_list l = List.fold_right insert l Leaf

确定发生的事情的链条。取出列表1,2,3。

首先，我们没有树并插入1 Leaf的结果。

调用此T1

接下来是通过插入2 T1生成的树

调用此T2

>

然后插入3 T2生成的树

这是Tree_of_list结果返回的结果。

如果我们调用T3的结果，那么在代码调用的其他地方插入4 T3时，从插入返回的结果与使用列表1,2,3,4调用Tree_of_list时没有区别。

Ok, I have written a binary search tree in 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 above code was said to be good in The right way to use a data structure in OCaml

However, I found a problem. This insert will only work when building a bst from a list in one go, such as

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

So if we build a bst from a list continuously, no problem, we can get a complete bst which has all nodes from the list.

However, if I have a bst built previously and now I wish to insert a node, then the resulting bst won't have complete nodes from the previous tree, am I right?

Then how should I write a bst in OCaml so that we create a new bst with all nodes from previous tree to keep the previous tree immutable? If every time I need to copy all nodes from old bst, will that impact the performance?

---

Edit:

So let's say initially, a bst is created with one node t1 = (10, Leaf, Leaf).

then I do let t2 = insert 5 t1, then I get t2 = (10, (5, Leaf, Leaf), Leaf), right? inside t2, let's give a variable c1 to the child node (5, Leaf, Leaf)

then I do let t5 = insert 12 t2, then I get t3 = (10, (5, Leaf, Leaf), (15, Leaf, Leaf)). let's give a variable c2 to the child node (5, Leaf, Leaf)

So my question is whether c1 == c2? Are the two (5, Leaf, Leaf)s in t2 and t3 exactly the same?

解决方案

Look at the accepted answer to the linked question. To be specific this line here:

let tree_of_list l = List.fold_right insert l Leaf

Work out the chain of what is happening. Take the list 1,2,3.

First we have no tree and the result of insert 1 Leaf.

call this T1

Next is the tree generated by insert 2 T1

call this T2

Then the tree generated by insert 3 T2

This is what is returned as the result of Tree_of_list.

If we call the result T3 then somewhere else in code call insert 4 T3 there is no difference in the result returned from insert than in calling Tree_of_list with the list 1,2,3,4.

这篇关于在OCaml中构建二进制搜索树的正确方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！