刪除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