I am creating an AVL Tree in Haskell but I am unsure of how to balance the tree. I can add elements in but they aren't balanced. like using the addList method I add in [4,2,1,3,6,8] adds it in as:
The layout for: Root 4 (Root 2 (Root 1 Empty Empty) (Root 2 Empty Empty)) (Root 6 Empty (Root 8 Empty Empty))
should be printed as:
4
2 6
1 3 8
I want to balance a tree right, but don't know how to implement it correctly, Here is my code so far, Any help on this would be amazing.
data AVLTree a = Empty | Root a (AVLTree a) (AVLTree a)
deriving (Eq, Ord, Show)
leaf a = Root a Empty Empty
addNode :: Integral a => a -> AVLTree a -> AVLTree a
addNode a Empty = leaf a
addNode x (Root a left right)
| x > a = Root a left (addNode x right)
| x < a = Root a (addNode x left) right
| otherwise = (Root a left right)
addList :: (Integral a) => [a] -> AVLTree a
addList [] = Empty
addList [n] = leaf n
addList (x:xs) = addNode x (addList xs)
search :: Integral a => AVLTree a -> a -> Bool
search Empty _ = False
search (Root a left right) x
| x == a = True
| x < a = search left x
| x > a = search right x
-- balance :: AVLTree a -> AVLTree a
-- balance Empty = Empty
-- balance tree
-- |(Root r (Root left (Root left1 Empty Empty) Empty) Empty) = (Root left left1 r) -- left left case
-- |(Root r Empty (Root right Empty Empty) (Root right Empty Empty)) = (Root right r right1) -- right right case
-- |(Root r (Root left Empty (Root right Empty Empty)) Empty) = (Root r (Root right (Root left Empty Empty) Empty) Empty) -- left right case
-- |(Root r Empty (Root right (Root left Empty Empty) Empty)) = (Root r Empty (Root left Empty (Root right Empty Empty))) -- right left case