Skip to content

Instantly share code, notes, and snippets.

@bssstudio
Last active December 31, 2015 15:59
Show Gist options
  • Select an option

  • Save bssstudio/8010747 to your computer and use it in GitHub Desktop.

Select an option

Save bssstudio/8010747 to your computer and use it in GitHub Desktop.
AVL tree insertion in haskell
data BinTree a = Leaf
| Node { nodeData :: a, left :: BinTree a, right :: BinTree a}
deriving (Eq, Show)
instance Functor BinTree where
fmap f Leaf = Leaf
fmap f (Node a l r) = Node (f a) (fmap f l) (fmap f r)
toList :: BinTree a -> [a]
toList Leaf = []
toList (Node a left right) = (toList left) ++ (a: (toList right))
insert :: Ord a => a -> BinTree a -> BinTree a
insert el Leaf = Node el Leaf Leaf
insert el (Node a l r)
| el <= a = Node a (insert el l) r
| otherwise = Node a l (insert el r)
insertAVL :: Ord a => a -> BinTree a -> BinTree a
insertAVL el Leaf = Node el Leaf Leaf
insertAVL el (Node a l r)
| el <= a = balanceSubtree (Node a (insertAVL el l) r)
| otherwise = balanceSubtree (Node a l (insertAVL el r))
isBalanced :: BinTree a -> Bool
isBalanced Leaf = True
isBalanced tree
| bf > 1 = False
| bf < -1 = False
| otherwise = True && (isBalanced (left tree)) && (isBalanced (right tree))
where bf = balanceFactor tree
balanceFactor :: BinTree a -> Int
balanceFactor Leaf = 0
balanceFactor (Node _ l r) = height l - height r
height :: BinTree a -> Int
height Leaf = 1
height (Node _ l r) = (max (height l) (height r)) + 1
balanceSubtree :: BinTree a -> BinTree a
balanceSubtree tree
| (bf <= 1) && (bf >= -1) = tree
| bf > 1 = balanceLeft tree
| bf < -1 = balanceRight tree
| otherwise = tree
where bf = balanceFactor tree
Node one left right = tree
balanceLeft tree
| bfl == -1 = let Node one (Node two a (Node three b c)) d = tree in
Node three (Node two a b) (Node one c d)
| otherwise = let Node one (Node two (Node three a b) c) d = tree in
Node two (Node three a b) (Node one c d)
where Node _ left right = tree
bfl = balanceFactor left
balanceRight tree
| bfr == 1 = let Node one a (Node two (Node three b c) d) = tree in
Node three (Node one a b) (Node two c d)
| otherwise = let Node one a (Node two b (Node three c d)) = tree in
Node two (Node one a b) (Node three c d)
where Node _ left right = tree
bfr = balanceFactor right
maxInTree :: BinTree a -> a
maxInTree (Node a _ Leaf) = a
maxInTree (Node a left right) = maxInTree right
deleteAVL :: Ord a => a -> BinTree a -> BinTree a
deleteAVL _ Leaf = Leaf
deleteAVL el (Node a left Leaf)
| el == a = left
| el < a = Node a (deleteAVL el left) Leaf
| otherwise = Node a left Leaf
deleteAVL el (Node a Leaf right)
| el == a = right
| el > a = Node a Leaf (deleteAVL el right)
| otherwise = Node a Leaf right
deleteAVL el (Node a left right)
| el == a = undefined
| el < a = Node a (deleteAVL el left) right
| otherwise = Node a left (deleteAVL el right)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment