[Haskell-beginners] How to delete a range from AVL tree.

Alexander.Vladislav.Popov alexander.vladislav.popov at gmail.com
Thu Sep 16 13:12:12 EDT 2010


Hi.

Help me to solve the problem I faced with.
I'm trying to delete items from the AVL tree 'itree' that are between 0 and 2.
But as you can see the result tree contains value of 1.


> import Data.Tree.AVL
> import Data.COrdering

> mydelete' :: (Ord a) => a -> a -> AVL a -> AVL a
> mydelete' p1 p2 tree = let res = delete cmp tree in
>                        case contains res cmp of
>                          True      -> mydelete' p1 p2 res
>                          otherwise -> res
>                        where
>                          cmp  = between p1 p2

> between a b x = if x < a
>                 then LT
>                 else if x > b
>                      then GT
>                      else EQ


> itree = push ((sndByCC compare) 3) 3 (pair 1 2)
> idel  = mydelete' 0 2

*Main> idel itree
P (Z E 1 E) 3 E
*Main> idel $ idel itree
P (Z E 1 E) 3 E
*Main>

Explain me why I got following results and where I made error.

*Main> (mydelete' 0 3) itree
E
*Main> (mydelete' 0 2) itree
P (Z E 1 E) 3 E
*Main> (mydelete' 1 2) itree
P (Z E 1 E) 3 E
*Main> (mydelete' 1 1) itree
Z (Z E 1 E) 2 (Z E 3 E)
*Main> (mydelete' 2 1) itree
Z (Z E 1 E) 2 (Z E 3 E)
*Main> (mydelete' 0 1) itree
Z (Z E 1 E) 2 (Z E 3 E)
*Main> (mydelete' 0 2) itree
P (Z E 1 E) 3 E
*Main> (mydelete' (-1) 2) itree
P (Z E 1 E) 3 E

Alexander


More information about the Beginners mailing list