在ocaml中插入BST

Question

插入：（'a，'b）btree->'a->'b->（'a，'b）btree

接受二进制搜索树，关键字和数据项，并返回与旧树相对应的新二进制搜索树，并在其中插入了给定关键字和数据项对。如果您使用Java或C等语言进行编程的经历使您感到困惑，请注意，我们不会在OCaml中修改旧树，但可以在构造新树时重用其中的部分内容。您应该假定输入树满足二叉搜索树上的有序不变量，并且您的函数应该保留该不变量。经常出现的另一个问题是：如果密钥已经出现在树中，该怎么办？我们通过以下方式解决此问题：新树不应该具有旧键和数据关联，而应该只有新树。

let rec insert (tree: ('a, 'b) btree) (k: 'a) (v: 'b) = 
  match tree with 
  | Empty ->  Node((k,v),Empty,Empty)
  | Node ((k',v'),l,r) -> 
      if k <= k' then Node((k',v') (insert b k v) r)
      else Node((k',v') l (insert c k v))

Answer 1

提示：(k',v') (insert b k v) r意味着将函数(k',v')应用于两个参数(insert b k v)和r。