pfds 3章 赤黒木

redBlackTree.hs

data Color = R | B deriving(Show, Eq)

data Ord a => RedBlackSet a = E | T Color (RedBlackSet a) a (RedBlackSet a)
  deriving (Show, Eq)

member :: Ord a => a -> RedBlackSet a -> Bool
member x E = False
member x (T _ a y b) | x < y = member x a
                     | x > y = member x b
                     | otherwise = True

balance B (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
balance B (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
balance B a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
balance B a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance c a x b = T c a x b

insert x s = T B a y b
  where
    ins E = T R E x E
    ins s@(T c a y b) | x < y = balance c (ins a) y b
                      | x > y = balance c a y (ins b)
                      | otherwise = s 
    T _ a y b = ins s

test1 = insert 1 E
test2 = insert 2 test1
test3 = insert 3 test2
test4 = insert 4 test3
test5 = insert 5 test4
test6 = insert 6 test5
test7 = insert 7 test6
test8 = insert 8 test7
test9 = insert 9 test8