Jean-Christophe Filliâtre wrote:
> Wow, that's impressive! But I guess you didn't need to implement the
remove
> operation on red-black trees :-) That's a real pain.
Is Kahrs' so bad:
delete :: Ord a => a -> RB a -> RB a
delete x t =
case del t of {T _ a y b -> T B a y b; _ -> E}
where
del E = E
del (T _ a y b)
| x<y = delformLeft a y b
| x>y = delformRight a y b
| otherwise = app a b
delformLeft a@(T B _ _ _) y b = balleft (del a) y b
delformLeft a y b = T R (del a) y b
delformRight a y b@(T B _ _ _) = balright a y (del b)
delformRight a y b = T R a y (del b)
balleft :: RB a -> a -> RB a -> RB a
balleft (T R a x b) y c = T R (T B a x b) y c
balleft bl x (T B a y b) = balance bl x (T R a y b)
balleft bl x (T R (T B a y b) z c) = T R (T B bl x a) y (balance b z (sub1
c))
balright :: RB a -> a -> RB a -> RB a
balright a x (T R b y c) = T R a x (T B b y c)
balright (T B a x b) y bl = balance (T R a x b) y bl
balright (T R a x (T B b y c)) z bl = T R (balance (sub1 a) x b) y (T B c z
bl)
sub1 :: RB a -> RB a
sub1 (T B a x b) = T R a x b
sub1 _ = error "invariance violation"
From:
http://www.cs.kent.ac.uk/people/staff/smk/redblack/Untyped.hs
Anyone got this in OCaml?
Cheers,
Jon.
--
Caml-list mailing list. Subscription management and archives:
https://sympa-roc.inria.fr/wws/info/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
