Anonymous user
AVL tree: Difference between revisions
no edit summary
(C++ solution addition) |
No edit summary |
||
Line 1,296:
}
</pre>
=={{header|Haskell}}==
=={{header|Scheme}}==
Line 1,612 ⟶ 1,614:
39=>''''
</pre>
=={{header|Haskell}}==
Solution of homework #4 from course http://www.seas.upenn.edu/~cis194/spring13/lectures.html.
<lang haskell>data Tree a = Leaf
| Node Integer (Tree a) a (Tree a)
deriving (Show, Eq)
foldTree :: Ord a => [a] -> Tree a
foldTree = foldr insert Leaf
next :: Tree a -> Tree a
next t = case t of
Leaf -> Leaf
(Node h left v right) -> rotate $ Node (parrenth left right) left v right
parrenth :: Tree a -> Tree a -> Integer
parrenth a b = 1 + max (height a) (height b)
height :: Tree a -> Integer
height Leaf = -1
height (Node h _ _ _) = h
insert :: Ord a => a -> Tree a -> Tree a
insert v' Leaf = Node 0 Leaf v' Leaf
insert v' t@(Node n left v right)
| v < v' = next $ Node n left v (insert v' right)
| v > v' = next $ Node n (insert v' left) v right
| otherwise = t
max' :: Ord a => Tree a -> Maybe a
max' Leaf = Nothing
max' (Node _ _ v right) = case right of
Leaf -> Just v
otherwise -> max' right
delete :: Ord a => a -> Tree a -> Tree a
delete x Leaf = Leaf
delete x (Node h left v right)
| x == v = case (max' right) of
Just m -> next $ Node h left m (delete m right)
Nothing -> left
| x > v = next $ Node h left v (delete x right)
| x < v = next $ Node h (delete x left) v right
rotate :: Tree a -> Tree a
rotate Leaf = Leaf
-- left left case
rotate (Node h (Node lh lleft lv lright) v right)
| lh-height(right) > 1 && height(lleft)-height(lright) >= 1 =
rotate $ Node lh lleft lv (Node (parrenth right lright) lright v right)
-- right right case
rotate (Node h left v (Node rh rleft rv rright))
| rh-height(left) > 1 && height(rright)-height(rleft) >= 1 =
rotate $ Node rh (Node (parrenth left rleft) left v rleft) rv rright
-- left right case
rotate (Node h (Node lh lleft lv (Node rh rleft rv rright)) v right)
| lh - height(right) > 1 && rh-height(lleft) >= 1 =
rotate $ Node h (Node (rh+1) (Node (lh-1) lleft lv rleft) rv rright) v right
-- right left case
rotate (Node h left v (Node rh (Node lh lleft lv lright) rv rright))
| rh-height(left) > 1 && lh-height(rright) >= 1 =
rotate $ Node h left v (Node (lh+1) lleft lv (Node (rh-1) lright rv rright))
rotate (Node h left v right) =
case (Node h (rotate left) v (rotate right)) of
(Node _ left' _ right') -> Node (parrenth left' right') left' v right'
draw :: Show a => Tree a -> String
draw t = "\n" ++ (draw' t 0) ++ "\n"
draw' :: Show a => Tree a -> Integer -> String
draw' Leaf _ = []
draw' (Node h left v right) deep = draw' right (deep+1)
++ [' ' | x <- [1..4*deep]] ++ show (v, h) ++ "\n"
++ draw' left (deep+1)</lang>
<pre>*Main> putStr $ draw $ delete 7 $ delete 2 $ foldTree [1..10]
(9,1)
(8,0)
(10,3)
(6,0)
(5,1)
(4,0)
(3,2)
(1,0)</pre>
| |||