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)