3

Type が定義されています: data Tree = Node Tree Tree | リーフ整数 | 無。メソッドdelete :: Tree -> Int -> Treeを作成して、2 番目のパラメーターで指定された特定の Int を持つすべてのリーフを削除します。

4

2 に答える 2

4

ツリーに特定の構造がない場合は、次のことができます

delete NIL _ = NIL
delete (Leaf i) int | i == int = NIL
                    | otherwise = Leaf i
delete (Node left right) int = Node (delete left int) (delete right int)

なんで？

delete NIL _ = NIL端にある空のツリーも含めて、すべてのケースに対処する必要があるためです。は_、気にしない値を表します。

delete (Leaf i) int | i == int = NIL
                    | otherwise = Leaf i

| i== int最初にノードを削除するかどうかを確認する必要があるためです。その場合、それを空の 3 に置き換えNILます。それ以外の場合は、そのままにしておきます。

delete (Node left right) int = Node (delete left int) (delete right int)ノードにいる場合、とサブツリーのint両方からを削除する必要があるためです。leftright

あなたはsの全負荷で終わるつもりはありませんNILか？

はい、そうなる可能性があると思います。あなたはで片付けることができます

prune (Node  NIL      NIL    ) = NIL
prune (Node (Leaf i)  NIL    ) = Leaf i 
prune (Node  NIL     (Leaf i)) = Leaf i 
prune (Node (Leaf i) (Leaf j)) = Node (Leaf i) (Leaf j)
prune (Node  left     right  ) = prune (Node (prune left) (prune right))
prune t = t

最初の 3 行は左、右、または両方の a を取り除きNIL、4 行目は 2 つの葉だけを残します。

5 行目は、このノードの左または右のサブツリーのいずれかがノードである場合にのみ呼び出されます。なんでprune三回？たぶん、あなたprune leftとprune rightそれらのうちの1人以上が終わったときNIL.

1枚ですっきりとした柄合わせprune t = tもお得です。NILLeaf i

于 2013-06-01T19:34:46.010 に答える
2

AndrewCの回答を改善することをお勧めします。彼の解決策は完全に正しいものですが、潜在的なパフォーマンスの問題があります。

問題は、関数deleteとprune関数の両方が、呼び出しごとにツリー全体の新しいコピーを作成することです。これは、要素が実際に削除されたかどうかに関係なく発生します。

最悪のシナリオは、存在しない要素を削除することです。

1M の整数を保持する非常に大きなツリーがあるとします。整数はリーフのみに格納されるため、ツリー全体には少なくとも 2M-1 のノードが含まれます。（または、ツリーがまだ剪定されていないため、NILノードが含まれている場合はさらに多くなります）。

このような巨大なツリーから存在しない要素を削除しようとすると、delete関数は 2M のノードすべてを複製するだけで何もしません。（そして、pruneそれらを再び複製します！）

既存の要素を削除することは、ほんの少しだけ良いことです。この場合、delete1 つのリーフを削除し、その親を更新して、残りのツリーを複製します。pruneおそらくさらにいくつかのノードが削除されますが、残りは複製されます。

なぜそれが起こるのですか？

重複が発生する場所は 2 つあります。

この行は、引数と完全に同一の新しいツリーを作成します。

delete (Leaf i) int | ...
                    | otherwise = Leaf i

また、この行は、要素が左右の分岐の両方に存在しない場合でも、新しいツリーを作成します。

delete (Node left right) int = Node (delete left int) (delete right int)

不必要な重複を避けることはできますか？

はい、もちろん。引数を変更しない場合は、引数を返すだけです。

これが私のバージョンです：

delete t i = fst $ delete' t i
  where delete' NIL _ = (NIL, True)
        delete' t@(Leaf i) int | i == int = (NIL, False)
                               | otherwise = (t, True)
        delete' t@(Node left right) int =
            let (left', unchangedLeft) = delete' left int
                (right', unchangedRight) = delete' right int
            in
              if unchangedLeft && unchangedRight
                then (t, True)
                else (Node left' right', False)

ご覧のとおりdelete'、(Tree, Bool) のペアを返すヘルパー関数を使用します。2 番目の要素は、ツリーが変更されていない場合は True、それ以外の場合は False です。

この関数は、ほとんどのノードを元のツリーと共有する新しいツリーを構築します。ルートから削除された要素へのパス上のノードのみを変更します。

どうpruneですか？

上記のバージョンはNIL要素を削除しません。NILAndrewC が指摘したように、複数の削除を実行した後、多くのsを持つツリーが作成される場合があります。この問題に対処するpruneには、同様の方法で変更するか、単純に に統合することができますdelete。

delete t i = fst $ delete'' t i
  where delete'' NIL _ = (NIL, True)
        delete'' t@(Leaf i) int | i == int = (NIL, False)
                                | otherwise = (t, True)
        delete'' t@(Node left right) int =
            let (left', unchangedLeft) = delete'' left int
                (right', unchangedRight) = delete'' right int
            in
              if unchangedLeft && unchangedRight
                then (t, True)
                else (newNode left' right', False)

        newNode NIL r = r
        newNode l NIL = l
        newNode l r = Node l r
于 2013-06-03T22:51:05.147 に答える