Advertisement
KillianMills

234Tree.hs

Dec 14th, 2014
41
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ----         Assignment 2
  2. ----Top-down 2-3-4 Trees in Haskell
  3.  
  4. ----Killian Mills, 11368701
  5.  
  6. --3 types of nodes, two three and four
  7. --implement an insertion function
  8. --search function
  9. --display function
  10.  
  11. --constrtuctors for the 2,3 and 4 trees
  12. data Tree t = Empty
  13.     | TwoTree t (Tree t)(Tree t)                                    -- first node type
  14.     | ThreeTree t t (Tree t)(Tree t)(Tree t)                        -- second node type
  15.     | FourTree t t t (Tree t)(Tree t)(Tree t)(Tree t)               -- third node type
  16.     deriving (Eq, Ord)
  17. -- two tree holds 1 element, has two children
  18. -- three tree holds 2 elements, has three children
  19. -- four tree holds 3 elements, has four children
  20.  
  21. --Test Tree
  22. myTree = TwoTree 15 (FourTree 2 4 8 (TwoTree 1 Empty Empty) (TwoTree 3 Empty Empty) (TwoTree 6 Empty Empty)
  23.     (TwoTree 9 Empty Empty)) (TwoTree 20 Empty (TwoTree 25 Empty Empty))
  24.  
  25.  
  26.    
  27. -------------- INSERT ---------------
  28. insert :: (Ord t) => t -> Tree t -> Tree t
  29.  
  30. --bases
  31. --1
  32. insert inputVal Empty = TwoTree inputVal Empty Empty
  33.  
  34. --2
  35. insert inputVal ( TwoTree firstVal Empty Empty)
  36.     | inputVal < firstVal = (ThreeTree inputVal firstVal Empty Empty Empty)                     -- input is first element
  37.     | inputVal > firstVal = (ThreeTree firstVal inputVal Empty Empty Empty)                     -- input is second element
  38.    
  39. --3
  40. insert inputVal ( ThreeTree firstVal secondVal Empty Empty Empty)
  41.     | inputVal < firstVal  = (FourTree inputVal firstVal secondVal Empty Empty Empty Empty)     -- input is first element
  42.     | inputVal > secondVal = (FourTree firstVal secondVal inputVal Empty Empty Empty Empty)     -- input is second element
  43.     | inputVal > firstVal  = (FourTree firstVal inputVal secondVal Empty Empty Empty Empty)     -- input is third element
  44.  
  45. --restructures 
  46. --1
  47. insert inputVal (TwoTree firstVal(FourTree left middle right Empty Empty Empty Empty ) (rightNode))                   -- 2 tree to 3 tree
  48.     = insert inputVal (ThreeTree middle firstVal (TwoTree left Empty Empty) (TwoTree right Empty Empty) (rightNode)) -- 2 vals, 3 children
  49.    
  50. --2
  51. insert inputVal (TwoTree firstVal (leftNode) (FourTree left middle right Empty Empty Empty Empty))                -- 2 tree to 3 tree
  52.     = insert inputVal (ThreeTree firstVal middle (leftNode) (TwoTree left Empty Empty) (TwoTree right Empty Empty )) -- 2 vals, 3 children
  53.    
  54. --3
  55. insert inputVal (ThreeTree firstVal secondVal(FourTree left middle right Empty Empty Empty Empty) (middleNode) (rightNode))              -- 3 tree to 4 tree
  56.     = insert inputVal (FourTree middle firstVal secondVal(TwoTree left Empty Empty) (TwoTree right Empty Empty)(middleNode)(rightNode)) -- 3 vals, 4 children
  57.    
  58. --4
  59. insert inputVal (ThreeTree firstVal secondVal (leftNode)(FourTree left middle right Empty Empty Empty Empty) (rightNode) )           -- 3 tree to 4 tree
  60.     = insert inputVal (FourTree middle firstVal secondVal (leftNode) (TwoTree left Empty Empty) (TwoTree right Empty Empty)(rightNode)) -- 3 vals, 4 children
  61.  
  62. --5
  63. insert inputVal (ThreeTree firstVal secondVal (leftNode) (middleNode) (FourTree left middle right Empty Empty Empty Empty ))              -- 3 tree to 4 tree
  64.     = insert inputVal (FourTree firstVal secondVal middle (leftNode) (middleNode) (TwoTree left Empty Empty)(TwoTree right Empty Empty)) -- 3 vals, 4 children
  65.    
  66. --6
  67. insert inputVal (FourTree firstVal secondVal thirdVal Empty Empty Empty Empty)                          -- 4 tree to 2 2 trees
  68.     = insert inputVal (TwoTree secondVal (TwoTree firstVal Empty Empty ) (TwoTree thirdVal Empty Empty )) -- 1 val, 2 children
  69.    
  70. --inserts
  71. --1
  72. insert inputVal (TwoTree firstVal (leftNode) (rightNode))                                                   -- two child nodes
  73.     | inputVal < firstVal = (TwoTree firstVal ( insert inputVal leftNode) (rightNode))
  74.     | inputVal > firstVal = (TwoTree firstVal (leftNode) ( insert inputVal rightNode))
  75.    
  76. --2
  77. insert inputVal (ThreeTree firstVal secondVal (leftNode) (middleNode) (rightNode))                          -- three child nodes
  78.     | inputVal < firstVal = ( ThreeTree firstVal secondVal (insert inputVal leftNode) middleNode rightNode)
  79.     | inputVal > firstVal && inputVal < secondVal = ( ThreeTree firstVal secondVal (leftNode) (insert inputVal middleNode) (rightNode))
  80.     | inputVal < firstVal && inputVal < secondVal = ( ThreeTree firstVal secondVal (leftNode) (middleNode) (insert inputVal rightNode))
  81.    
  82. --3
  83. insert inputVal (FourTree firstVal secondVal thirdVal (leftNode) (middle1Node) (middle2Node) (rightNode))   -- four child nodes
  84.     | inputVal < firstVal =  (FourTree firstVal secondVal thirdVal (insert inputVal leftNode) (middle1Node) (middle2Node) (rightNode))
  85.     | inputVal > thirdVal =  (FourTree firstVal secondVal thirdVal (leftNode) (middle1Node) (middle2Node) (insert inputVal rightNode))
  86.     | inputVal < secondVal = (FourTree firstVal secondVal thirdVal (leftNode) (insert inputVal middle1Node) (middle2Node) (rightNode))
  87.     | inputVal > secondVal = (FourTree firstVal secondVal thirdVal (leftNode) (middle1Node) (insert inputVal middle2Node) (rightNode))
  88.  
  89.    
  90.    
  91. -------------- SEARCH ---------------
  92.  
  93. search :: (Ord t) => Tree t -> t -> Bool
  94.  
  95. --empty tree
  96. search Empty inputVal = False
  97.  
  98. --2 tree
  99. search (TwoTree firstVal (leftNode) (rightNode)) inputVal                                           -- two child nodes
  100.     | inputVal == firstVal = True   -- found input
  101.     | inputVal < firstVal = search leftNode inputVal
  102.     | inputVal > firstVal = search rightNode inputVal
  103.  
  104. --3 tree
  105. search (ThreeTree firstVal secondVal (leftNode) (middleNode) (rightNode)) inputVal                      -- three child nodes
  106.     | inputVal == firstVal || inputVal == secondVal = True  -- found input
  107.     | inputVal < firstVal  = search leftNode inputVal
  108.     | inputVal > secondVal = search rightNode inputVal
  109.     | inputVal > firstVal && inputVal < secondVal = search middleNode inputVal
  110.    
  111. --4 tree
  112. search (FourTree firstVal secondVal thirdVal (leftNode) (middle1Node) (middle2Node) (rightNode)) inputVal   -- four child nodes
  113.     | inputVal == firstVal || inputVal == secondVal || inputVal == thirdVal = True  -- found input
  114.     | inputVal < firstVal = search leftNode inputVal
  115.     | inputVal > thirdVal = search rightNode inputVal
  116.     | inputVal > firstVal && inputVal < secondVal = search middle1Node inputVal
  117.     | inputVal > secondVal && inputVal < thirdVal  = search middle2Node inputVal       
  118.  
  119.    
  120.    
  121. -------------- DISPLAY ---------------
  122.  
  123. --display
  124.  
  125. instance Show a => Show (Tree a) where
  126.    show t = displayFormat t
  127.  
  128. indent :: [String] -> [String]
  129. indent = map ("          "++)
  130.  
  131. --Empty case
  132. displayTree Empty = []
  133.  
  134. --Two Tree case
  135. displayTree (TwoTree firstVal (leftNode) (rightNode))
  136.     = indent (displayTree rightNode) ++ ["[ " ++ show firstVal ++ " ]"] ++ indent (displayTree leftNode)
  137.  
  138. --Three Tree case  
  139. displayTree (ThreeTree firstVal secondVal (leftNode) (middleNode) (rightNode))
  140.     = indent (displayTree rightNode ) ++ ["[ " ++ show firstVal ++ " " ++ show secondVal ++ " ]"] ++ indent (displayTree middleNode) ++ indent (displayTree leftNode)
  141.  
  142. --Four Tree case
  143. displayTree (FourTree firstVal secondVal thirdVal (leftNode) (middle1Node) (middle2Node) (rightNode))
  144.     = indent (displayTree rightNode) ++ indent (displayTree middle2Node) ++ ["[ " ++ show firstVal ++ " " ++ show secondVal ++ " " ++ show thirdVal ++ " ]"] ++ indent (displayTree middle1Node) ++ indent (displayTree leftNode)
  145.  
  146. displayFormat :: (Show t) => Tree t -> String
  147. displayFormat = unlines.displayTree
  148.  
  149. display :: (Show t) => Tree t -> IO ()
  150. display t = putStr (displayFormat t)
  151.    
  152.    
  153.    
  154. ---- END ----
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement