今のところ、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検索パスに沿っています。
私の質問は、このコピーを回避する方法はありますか?
この質問はExercise 2.3、書籍Purely Functional Data Structuresからのものです。
演習 2.3 既存の要素を二分探索木に挿入すると、コピーされたノードが元のノードと区別できなくても、検索パス全体がコピーされます。このコピーを避けるために、例外を使用して挿入を書き直してください。反復ごとに 1 つのハンドラーではなく、挿入ごとに 1 つのハンドラーのみを確立します。
私は実際には運動についていけません。
- 「このコピーを避けるために例外を使用する」とはどういう意味ですか?
- 「例外」を使用する理由
- 「挿入ごとに1つのハンドラー」とはどういう意味ですか?