Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ---- Assignment 2
- ----Top-down 2-3-4 Trees in Haskell
- ----Killian Mills, 11368701
- --3 types of nodes, two three and four
- --implement an insertion function
- --search function
- --display function
- --constrtuctors for the 2,3 and 4 trees
- data Tree t = Empty
- | TwoTree t (Tree t)(Tree t) -- first node type
- | ThreeTree t t (Tree t)(Tree t)(Tree t) -- second node type
- | FourTree t t t (Tree t)(Tree t)(Tree t)(Tree t) -- third node type
- deriving (Eq, Ord)
- -- two tree holds 1 element, has two children
- -- three tree holds 2 elements, has three children
- -- four tree holds 3 elements, has four children
- --Test Tree
- myTree = TwoTree 15 (FourTree 2 4 8 (TwoTree 1 Empty Empty) (TwoTree 3 Empty Empty) (TwoTree 6 Empty Empty)
- (TwoTree 9 Empty Empty)) (TwoTree 20 Empty (TwoTree 25 Empty Empty))
- -------------- INSERT ---------------
- insert :: (Ord t) => t -> Tree t -> Tree t
- --bases
- --1
- insert inputVal Empty = TwoTree inputVal Empty Empty
- --2
- insert inputVal ( TwoTree firstVal Empty Empty)
- | inputVal < firstVal = (ThreeTree inputVal firstVal Empty Empty Empty) -- input is first element
- | inputVal > firstVal = (ThreeTree firstVal inputVal Empty Empty Empty) -- input is second element
- --3
- insert inputVal ( ThreeTree firstVal secondVal Empty Empty Empty)
- | inputVal < firstVal = (FourTree inputVal firstVal secondVal Empty Empty Empty Empty) -- input is first element
- | inputVal > secondVal = (FourTree firstVal secondVal inputVal Empty Empty Empty Empty) -- input is second element
- | inputVal > firstVal = (FourTree firstVal inputVal secondVal Empty Empty Empty Empty) -- input is third element
- --restructures
- --1
- insert inputVal (TwoTree firstVal(FourTree left middle right Empty Empty Empty Empty ) (rightNode)) -- 2 tree to 3 tree
- = insert inputVal (ThreeTree middle firstVal (TwoTree left Empty Empty) (TwoTree right Empty Empty) (rightNode)) -- 2 vals, 3 children
- --2
- insert inputVal (TwoTree firstVal (leftNode) (FourTree left middle right Empty Empty Empty Empty)) -- 2 tree to 3 tree
- = insert inputVal (ThreeTree firstVal middle (leftNode) (TwoTree left Empty Empty) (TwoTree right Empty Empty )) -- 2 vals, 3 children
- --3
- insert inputVal (ThreeTree firstVal secondVal(FourTree left middle right Empty Empty Empty Empty) (middleNode) (rightNode)) -- 3 tree to 4 tree
- = insert inputVal (FourTree middle firstVal secondVal(TwoTree left Empty Empty) (TwoTree right Empty Empty)(middleNode)(rightNode)) -- 3 vals, 4 children
- --4
- insert inputVal (ThreeTree firstVal secondVal (leftNode)(FourTree left middle right Empty Empty Empty Empty) (rightNode) ) -- 3 tree to 4 tree
- = insert inputVal (FourTree middle firstVal secondVal (leftNode) (TwoTree left Empty Empty) (TwoTree right Empty Empty)(rightNode)) -- 3 vals, 4 children
- --5
- insert inputVal (ThreeTree firstVal secondVal (leftNode) (middleNode) (FourTree left middle right Empty Empty Empty Empty )) -- 3 tree to 4 tree
- = insert inputVal (FourTree firstVal secondVal middle (leftNode) (middleNode) (TwoTree left Empty Empty)(TwoTree right Empty Empty)) -- 3 vals, 4 children
- --6
- insert inputVal (FourTree firstVal secondVal thirdVal Empty Empty Empty Empty) -- 4 tree to 2 2 trees
- = insert inputVal (TwoTree secondVal (TwoTree firstVal Empty Empty ) (TwoTree thirdVal Empty Empty )) -- 1 val, 2 children
- --inserts
- --1
- insert inputVal (TwoTree firstVal (leftNode) (rightNode)) -- two child nodes
- | inputVal < firstVal = (TwoTree firstVal ( insert inputVal leftNode) (rightNode))
- | inputVal > firstVal = (TwoTree firstVal (leftNode) ( insert inputVal rightNode))
- --2
- insert inputVal (ThreeTree firstVal secondVal (leftNode) (middleNode) (rightNode)) -- three child nodes
- | inputVal < firstVal = ( ThreeTree firstVal secondVal (insert inputVal leftNode) middleNode rightNode)
- | inputVal > firstVal && inputVal < secondVal = ( ThreeTree firstVal secondVal (leftNode) (insert inputVal middleNode) (rightNode))
- | inputVal < firstVal && inputVal < secondVal = ( ThreeTree firstVal secondVal (leftNode) (middleNode) (insert inputVal rightNode))
- --3
- insert inputVal (FourTree firstVal secondVal thirdVal (leftNode) (middle1Node) (middle2Node) (rightNode)) -- four child nodes
- | inputVal < firstVal = (FourTree firstVal secondVal thirdVal (insert inputVal leftNode) (middle1Node) (middle2Node) (rightNode))
- | inputVal > thirdVal = (FourTree firstVal secondVal thirdVal (leftNode) (middle1Node) (middle2Node) (insert inputVal rightNode))
- | inputVal < secondVal = (FourTree firstVal secondVal thirdVal (leftNode) (insert inputVal middle1Node) (middle2Node) (rightNode))
- | inputVal > secondVal = (FourTree firstVal secondVal thirdVal (leftNode) (middle1Node) (insert inputVal middle2Node) (rightNode))
- -------------- SEARCH ---------------
- search :: (Ord t) => Tree t -> t -> Bool
- --empty tree
- search Empty inputVal = False
- --2 tree
- search (TwoTree firstVal (leftNode) (rightNode)) inputVal -- two child nodes
- | inputVal == firstVal = True -- found input
- | inputVal < firstVal = search leftNode inputVal
- | inputVal > firstVal = search rightNode inputVal
- --3 tree
- search (ThreeTree firstVal secondVal (leftNode) (middleNode) (rightNode)) inputVal -- three child nodes
- | inputVal == firstVal || inputVal == secondVal = True -- found input
- | inputVal < firstVal = search leftNode inputVal
- | inputVal > secondVal = search rightNode inputVal
- | inputVal > firstVal && inputVal < secondVal = search middleNode inputVal
- --4 tree
- search (FourTree firstVal secondVal thirdVal (leftNode) (middle1Node) (middle2Node) (rightNode)) inputVal -- four child nodes
- | inputVal == firstVal || inputVal == secondVal || inputVal == thirdVal = True -- found input
- | inputVal < firstVal = search leftNode inputVal
- | inputVal > thirdVal = search rightNode inputVal
- | inputVal > firstVal && inputVal < secondVal = search middle1Node inputVal
- | inputVal > secondVal && inputVal < thirdVal = search middle2Node inputVal
- -------------- DISPLAY ---------------
- --display
- instance Show a => Show (Tree a) where
- show t = displayFormat t
- indent :: [String] -> [String]
- indent = map (" "++)
- --Empty case
- displayTree Empty = []
- --Two Tree case
- displayTree (TwoTree firstVal (leftNode) (rightNode))
- = indent (displayTree rightNode) ++ ["[ " ++ show firstVal ++ " ]"] ++ indent (displayTree leftNode)
- --Three Tree case
- displayTree (ThreeTree firstVal secondVal (leftNode) (middleNode) (rightNode))
- = indent (displayTree rightNode ) ++ ["[ " ++ show firstVal ++ " " ++ show secondVal ++ " ]"] ++ indent (displayTree middleNode) ++ indent (displayTree leftNode)
- --Four Tree case
- displayTree (FourTree firstVal secondVal thirdVal (leftNode) (middle1Node) (middle2Node) (rightNode))
- = indent (displayTree rightNode) ++ indent (displayTree middle2Node) ++ ["[ " ++ show firstVal ++ " " ++ show secondVal ++ " " ++ show thirdVal ++ " ]"] ++ indent (displayTree middle1Node) ++ indent (displayTree leftNode)
- displayFormat :: (Show t) => Tree t -> String
- displayFormat = unlines.displayTree
- display :: (Show t) => Tree t -> IO ()
- display t = putStr (displayFormat t)
- ---- END ----
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement