data SplayTree a = EmptyTree | Node a (SplayTree a) (SplayTree a) deriving (Show) -- Use in-order travels to put the tree data into a list flatten :: SplayTree a -> [a] flatten EmptyTree = [] flatten (Node rootValue leftSubtree rightSubtree) = (flatten leftSubtree) ++ [rootValue] ++ (flatten rightSubtree) -- Calculate the number of elements of a tree size :: SplayTree a -> Int size EmptyTree = 0 size (Node rootValue leftSubtree rightSubtree) = 1 + (size leftSubtree) + (size rightSubtree) -- Calculate the height of a tree height :: SplayTree a -> Int height EmptyTree = 0 height (Node rootValue leftSubtree rightSubtree) = 1 + (max (height leftSubtree) (height rightSubtree)) -- Return the depth of a value without splaying, requires the value to be present depth :: (Ord a) => a -> SplayTree a -> Int depth value EmptyTree = error "Cannot find depth of an element not in the tree" depth value (Node rootValue leftSubtree rightSubtree) | value < rootValue = 1 + (depth value leftSubtree) | value == rootValue = 0 | value > rootValue = 1 + (depth value rightSubtree) -- Insert an element into the tree if it is not present and move that element to the root. -- The process guarentees not other elemet's depth is changed by more than one. insert :: (Ord a) => a -> SplayTree a -> SplayTree a insert value EmptyTree = Node value EmptyTree EmptyTree insert value (Node rootValue leftSubtree rightSubtree) | value < rootValue = let insertResult = insert value leftSubtree in case insertResult of EmptyTree -> error "EmptyTree cannot be result of insert" Node resultRootValue resultLeftSubtree resultRightSubtree -> Node value resultLeftSubtree (Node rootValue resultRightSubtree rightSubtree) | value == rootValue = Node rootValue leftSubtree rightSubtree | value > rootValue = let insertResult = insert value rightSubtree in case insertResult of EmptyTree -> error "EmptyTree cannot be result of insert" Node resultRootValue resultLeftSubtree resultRightSubtree -> Node value (Node rootValue leftSubtree resultLeftSubtree) resultRightSubtree -- Determine is an element occurs in the tree. If so move that element to the root. -- The process guarentees not other elemet's depth is changed by more than one. -- occurs :: (Ord a) => a -> SplayTree a -> (Bool, SplayTree a)