Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- module Baum (
- Baum,
- searchElement,
- insertElement,
- harry,
- balance
- ) where
- data (Ord a, Eq a)=> Baum a = Nil | Node Bool (Baum a) a (Baum a) deriving Show
- harry = Node True (Node False Nil 1 Nil) 6 (Node False Nil 8 Nil)
- searchElement x Nil = False
- searchElement x (Node _ l a r)=
- if x<a then searchElement x l
- else if x>a then searchElement x r
- else True
- insertElement x Nil = Node True Nil x Nil
- insertElement x s = ins (Node False Nil x Nil) s
- where ins (Node u i dat o) (Node q a y b)
- | dat<y = balance (Node q (ins (Node False Nil dat Nil) a) y b)
- | dat>y = balance (Node q a y (ins (Node False Nil dat Nil) b))
- | otherwise = s
- balance (Node True (Node False (Node False a x b) y c) z d) = ( Node False ( Node True a x b ) y ( Node True c z d)) -- s 1lr 2lr --> s 1lr 1rr
- balance (Node True (Node False a x (Node False b y c )) z d) = ( Node False ( Node True a x b ) y ( Node True c z d)) -- s 1lr 2rr --> s 1lr 1rr
- balance (Node True a x ( Node False (Node False b y c) z d)) = ( Node False ( Node True a x b ) y ( Node True c z d)) -- s 1rr 2lr --> s 1lr 1rr
- balance (Node True a x ( Node False b y (Node False c z d))) = ( Node False ( Node True a x b ) y ( Node True c z d)) -- s 1rr 2rr --> s 1lr 1rr
Add Comment
Please, Sign In to add comment