How to delete a range from AVL tree.
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
Excuse me for the repost.
I'm sending it again because I have not find a reply from
beginners-bounces@haskell.org and I want to exclude (possible) problems
related to the mailing list.
I would be very much appritiated for any help or advice.
Alexander.
2010/9/16 Alexander.Vladislav.Popov
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
Hello Alexander I suspect mydelete' isn't working because it needs a "sorted" tree - either the initial tree you are supplying isn't sorted or it becomes unsorted after one delete step. I don't know the AVL library at all (I only installed it now to look at your problem) so I can't say from looking at the constructors whether the problem tree is malformed, the problem tree being:
P (Z E 1 E) 3 E
Potentially very few people use the Avl module which is why you haven't had a reply yet. You could try posting to the Cafe instead if you don't get a better answer. Best wishes Stephen
I think that your compare function has the result inverted, you could try: between a b x | x < a = GT | x > b = LT | otherwise = EQ I think that the tree is correct. On Fri, 2010-09-17 at 08:41 +0100, Stephen Tetley wrote:
Hello Alexander
I suspect mydelete' isn't working because it needs a "sorted" tree - either the initial tree you are supplying isn't sorted or it becomes unsorted after one delete step.
I don't know the AVL library at all (I only installed it now to look at your problem) so I can't say from looking at the constructors whether the problem tree is malformed, the problem tree being:
P (Z E 1 E) 3 E
Potentially very few people use the Avl module which is why you haven't had a reply yet. You could try posting to the Cafe instead if you don't get a better answer.
Best wishes
Stephen _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
Thank you very much, Stephen and Jean!
I guess I missed something in my tests.
You definition gives me valid results.
How I can missed it!
Thank you very much again!
2010/9/17 jean verdier
I think that your compare function has the result inverted, you could try:
between a b x | x < a = GT | x > b = LT | otherwise = EQ
I think that the tree is correct.
On Fri, 2010-09-17 at 08:41 +0100, Stephen Tetley wrote:
Hello Alexander
I suspect mydelete' isn't working because it needs a "sorted" tree - either the initial tree you are supplying isn't sorted or it becomes unsorted after one delete step.
I don't know the AVL library at all (I only installed it now to look at your problem) so I can't say from looking at the constructors whether the problem tree is malformed, the problem tree being:
P (Z E 1 E) 3 E
Potentially very few people use the Avl module which is why you haven't had a reply yet. You could try posting to the Cafe instead if you don't get a better answer.
Best wishes
Stephen _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
participants (3)
-
Alexander.Vladislav.Popov -
jean verdier -
Stephen Tetley