Last active
December 31, 2015 15:59
-
-
Save bssstudio/8010747 to your computer and use it in GitHub Desktop.
AVL tree insertion in haskell
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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