haskellのバイナリ検索ツリーの関数を削除する

Question

バイナリ検索ツリーの要素を削除する関数を実装するにはどうすればよいですか？ これは私の木である：

data Tree a = Leaf 
      | Node a (Tree a) (Tree a) 

私は場合には、私の木が葉

delete :: (Ord a) => a -> Tree a -> Tree a 
delete _ Leaf = Leaf 

と左ケースと右にあることを知っているが空ではありませんが、私は右から最小値を削除する必要があります（または左から最大）、それがルートになりました。しかし、私はそれをどのように実装できますか？

Answer 1

あなたは木から最小の要素を削除、変更ツリーと最小要素の両方を返す関数

delMin :: Tree a -> (Tree a, a) 

を実装する必要があります。次に、削除アルゴリズムは次のようになります。削除するアイテムのノードを見つけて

-- delete' n deletes the node n and returns a modified BST 
delete' :: Ord a => Tree a -> Tree a 
delete' (Node _ l Leaf) = l 
delete' (Node _ Leaf r) = r 
delete' (Node _ l r)  = let (r', min) = delMin r in 
           Node min l r'