functional-programming - 插入 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 StructuresExercise 2.3一书：

练习 2.3 将现有的 eleemtn 插入二叉搜索树会复制整个搜索路径，即使复制的节点与原始节点无法区分。使用异常重写插入以避免这种复制。每次插入只建立一个处理程序，而不是每次迭代建立一个处理程序。

我实际上完全不遵循这个练习。

1. “使用异常来避免这种复制”是什么意思？
2. 为什么要使用“例外”？
3. 什么是“每次插入一个处理程序”？

Answer 1

请注意，只有在插入已经存在的元素时才能避免复制！不难看出如何做到这一点。