如何避免在插入BST時複製/創建新節點

Question

現在讓我們忽略BST的平衡部分。

type 'a bst = 
    | Leaf 
    | Node of 'a bst * 'a * 'a bst 

典型insert看起來就像這樣：

let rec insert x = function 
    | Leaf -> Node (Leaf, x, Leaf) 
    | Node (l, k, r) as n -> 
    if x = k then n 
    else if x < k then Node (insert x l, k, r) 
    else Node (l, k, insert x r) 

毫無疑問，功能insert將create new nodes/make a copy of nodes搜索路徑。

所以我的問題是有沒有辦法避免這種複製？

這個問題來自於書Purely Functional Data Structures的Exercise 2.3：

練習2.3插入現有eleemtn成二叉搜索樹 會將整個搜索路徑，即使複製節點是從原件 沒有區別。使用例外 重寫插入以避免此複製。每個插入僅建立一個處理程序，而不是每個迭代一個處理程序。

我其實不太喜歡這個練習。

1. 什麼意思是「使用異常來避免這種複製」？
2. 爲什麼要使用「例外」？
3. 什麼意思是「每個插入一個處理程序」？

Answer 1

請注意，只有在插入已經存在的元素時才能避免複製！應該不難看出如何做到這一點。