1

私はbinary search treeOCamlでの操作を構築しています。

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)

私のdeletionコードが十分であるかどうか、または改善されているかどうかを誰か教えてもらえますか?

4

1 に答える 1

2

1 つの改善点は、ツリーにあるものを挿入する場合、またはツリーにないものを削除する場合です。これらの各操作は、その特定のノードへの検索パスを複製します。そのキーの値を更新する必要があるため、挿入はおそらく問題ありませんが、削除は改善できる場合です。これは、関数を例外でラップして元のツリーを返すことで解決できます。

ツリーにないものを削除すると、次のようになります。再帰するNodeと、正しいサブツリーで削除されたキーで新しいものを作成します。この特定のケースでは、delete 関数は に再帰し、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
于 2013-03-11T17:22:00.370 に答える