Delete function in binary search tree in haskell

Question

How can I implement a function to delete an element in a binary search tree? This is my tree:

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

I know that in case my tree is a Leaf

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

and in case left and right are not empty, I have to delete the minimum from right (or maximum from left) and it became the root. But, how can I implement it??

Then please tag it so next time. It's common practice here.

Matvey Aksenov
– Matvey Aksenov

2012-02-22 15:47:11 +00:00
Commented Feb 22, 2012 at 15:47 — Matvey Aksenov
– Matvey Aksenov, Commented Feb 22, 2012 at 15:47
@MatveyB.Aksenov oh, sorry. next time I'll remember

Marco Sero
– Marco Sero

2012-02-22 19:22:53 +00:00
Commented Feb 22, 2012 at 19:22 — Marco Sero
– Marco Sero, Commented Feb 22, 2012 at 19:22

Fred Foo · Accepted Answer · 2012-02-22 11:18:39Z

1

You should implement a function

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

that deletes the minimum element from a tree and returns both the modified tree and the minimum element. Then the deletion algorithm becomes: find the node with the item to be deleted and call

-- 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'

answered Feb 22, 2012 at 11:18

Fred Foo

365k80 gold badges765 silver badges852 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Daniel Fischer Over a year ago

If delMin is top-level, it is probably good to make it delMin :: Tree a -> Maybe (Tree a, a) to deal with Leaf.

Fred Foo Over a year ago

@DanielFischer: delMin, at least in current should not be exported from the BST module. It might be hidden in a where clause.

Daniel Fischer Over a year ago

It might be considered generally useful, though, so if it is exposed, I'd rather safely deal with Leaf. If it's just a local, that would of course be unnecessary clutter.

Collectives™ on Stack Overflow

Delete function in binary search tree in haskell

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related