SkewTrees

SkewTree.hs

type Height = Int

data SkewTree a = Empty
                | TopNode !Height !(SkewTree a) a !(SkewTree a) !(SkewTree a)
                | InternalNode !Height !(SkewTree a) a !(SkewTree a)
                deriving (Show,Eq)


-- data SkewTree a = Empty
--                 | TopNode !Height !(SkewTree a) a !(SkewTree a) !(SkewTree a)
--                 | InternalNode !Height !(SkewTree a) a !(SkewTree a)
--                 deriving (Show,Eq)


leaf a = InternalNode 1 Empty a Empty

height Empty = 0
height (TopNode h _ _ _ _) = h
height (InternalNode h _ _ _ ) = h


splitToInternal (TopNode h l x r n) = (InternalNode h l x r, n)
splitToInternal Empty               = error "splitToInternal: Empty"
splitToInternal _                   = error "splitToInternal: InternalNode"

isEmpty Empty = True
isEmpty _     = False

insert x Empty = TopNode 1 Empty x Empty Empty
insert x t     = let (l,t') = splitToInternal t
                     (r,n)  = splitToInternal t'
                 in if (not $ isEmpty t' ) && height l == height r
                    then TopNode (height l + 1) l     x r     n
                    else TopNode 1              Empty x Empty t



lookup' x Empty = False
lookup' x (InternalNode _ l y r) = or [x == y, lookup' x l, lookup' x r]
lookup' x (TopNode _ l y r n)    = or [x == y, lookup' x l, lookup' x r, lookup' x n]