删除OCaml中的二进制搜索树

Question

我正在OCaml中构建binary search tree的操作。

type ('a, 'b) bst = 
    | Node of 'a * 'b * ('a, 'b) bst * ('a, 'b) bst 
    | Leaf;; 

let rec insert k v = function 
    | Leaf -> Node (k, v, Leaf, Leaf) 
    | Node (k', v', left, right) -> 
    if k < k' then Node (k', v', insert k v left, right) 
    else if k = k' then Node (k, v, left, right) 
    else Node (k', v', left, insert k v right);; 

let rec delete k = function 
    | Leaf -> Leaf 
    | Node (k', v, l, r) as p -> 
    if k < k' then Node (k', v, (delete k l),r) 
    else if k > k' then Node (k', v, l, (delete k r)) 
    else 
    match (l, r) with 
     | (Leaf, Leaf) -> Leaf 
     | (l, Leaf) -> l 
     | (Leaf, r) -> r 
     | (_, _) -> 
     let Node (km, vm, _, _) = max l in 
     Node (km, vm, delete km l, Leaf) 

谁能告诉我，我的​​代码是否足够或改善好？

Answer 1

当我们插入树中的东西，或者删除不在树中的东西时，一种改进就是这种情况。这些操作中的每一个都将复制到该特定节点的搜索路径。插入可能不是问题，因为您需要更新该密钥的值，但删除会是您可以进行改进的情况。这可以通过将函数包装成异常来解决，以返回原始树。

下面是删除看起来像不在树中的东西。在递归时，您创建一个新的Node，并在正确的子树中删除密钥。在这种特殊情况下，删除功能将递归到Leaf，然后返回Leaf并且在每一步备份堆栈返回新构建的Node。这条新路径表示为下面的蓝色路径。由于没有结构将新路径展开到旧路径，因此我们在结果树中重新创建搜索路径。

let at = delete x bt 

要在异常修复这个问题，如前所述包装的功能。

let delete k t = 
    let rec delete k = function 
     | Leaf -> raise Not_found 
     ... 
    in 
    try delete k t with Not_found -> t