Guest User

Untitled

a guest
Aug 16th, 2018
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.29 KB | None | 0 0
  1. module Baum (
  2. Baum,
  3. searchElement,
  4. insertElement,
  5. harry,
  6. balance
  7. ) where
  8.  
  9. data (Ord a, Eq a)=> Baum a = Nil | Node Bool (Baum a) a (Baum a) deriving Show
  10.  
  11. harry = Node True (Node False Nil 1 Nil) 6 (Node False Nil 8 Nil)
  12.  
  13. searchElement x Nil = False
  14. searchElement x (Node _ l a r)=
  15. if x<a then searchElement x l
  16. else if x>a then searchElement x r
  17. else True
  18.  
  19. insertElement x Nil = Node True Nil x Nil
  20. insertElement x s = ins (Node False Nil x Nil) s
  21. where ins (Node u i dat o) (Node q a y b)
  22. | dat<y = balance (Node q (ins (Node False Nil dat Nil) a) y b)
  23. | dat>y = balance (Node q a y (ins (Node False Nil dat Nil) b))
  24. | otherwise = s
  25.  
  26. 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
  27. 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
  28. 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
  29. 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