This is my first attempt at learning binary trees. I'm looking for general feedback on how it could be made cleaner, more idiomatic, or more efficient.
data Tree a = ETree | Node (Tree a) (Tree a) a deriving (Show)
tInsert :: Ord o => o -> Tree o -> Tree o
tInsert x ETree = Node ETree ETree x
tInsert x (Node lT rT a)
| x < a = Node (tInsert x lT) rT a
| x > a = Node lT (tInsert x rT) a
| otherwise = Node lT rT x
-- Folds a list into a tree
tFromListL, tFromListR :: Ord o => [o] -> Tree o
tFromListL = foldl (flip tInsert) ETree
tFromListR = foldr tInsert ETree
-- Turns a tree into a list
tToList :: Ord o => Tree o -> [o]
tToList ETree = []
tToList (Node lT rT a) = (tToList lT) ++ [a] ++ (tToList rT)
-- Splits a list roughly in half (as part of balancing)
splitInHalf :: [a] -> ([a],[a])
splitInHalf xs = splitAt (round $ (fromIntegral $ length xs) / 2.0) xs
-- Returns how unbalanced a node is
tUnbalancedBy :: Tree a -> Int
tUnbalancedBy ETree = 0
tUnbalancedBy (Node lT rT _) = absDiff (tDepth lT) (tDepth rT)
-- Arranges a list in such a way that it forms a more balanced tree
balanceList :: [a] -> [a]
balanceList xs = let (fH,sH) = splitInHalf xs in (reverse fH) ++ sH
-- "Inefficient balance"
tIneffBalance :: Ord o => Tree o -> Tree o
tIneffBalance = tFromListL . balanceList . tToList
-- Finds the min/max values of a tree
tMin, tMax :: Ord o => Tree o -> o
tMin ETree = error "tMin called on an Empty Tree"
tMin (Node lT _ a) = case lT of
ETree -> a
(Node lT' _ _) -> tMin lT'
tMax ETree = error "tMax called on an Empty Tree"
tMax (Node _ rT a) = case rT of
ETree -> a
(Node _ rT' _) -> tMax rT'
-- Find the max depth of a tree
tDepth :: Tree a -> Int
tDepth ETree = 0
tDepth (Node lT rT _) = 1 + max (tDepth lT) (tDepth rT)
-- Finds how many nodes a tree contains
tSize :: Tree a -> Int
tSize ETree = 0
tSize (Node lT rT _) = 1 + (tSize lT) + (tSize rT)
absDiff :: Int -> Int -> Int
absDiff x y = abs $ x - y
-- Checks if a node is balanced
tIsBalanced :: Tree a -> Bool
tIsBalanced ETree = True
tIsBalanced n
| tUnbalancedBy n > 2 = False
| otherwise = True
-- Checks if a value is an element of the tree
tElem :: Ord o => o -> Tree o -> Bool
tElem x ETree = False
tElem x (Node lT rT a)
| x < a = tElem x lT
| x > a = tElem x rT
| otherwise = True
tDelete :: Ord o => o -> Tree o -> Tree o
tDelete _ ETree = ETree
tDelete _ n@(Node ETree ETree _) = n -- Or give "Not found" error?
tDelete tD n@(Node lT rT a)
| tD < a = Node (tDelete tD lT) rT a
| tD > a = Node lT (tDelete tD rT) a
| otherwise = case (lT,rT) of
(ETree,t) -> t
(t,ETree) -> t
(t,t') -> let fMin = tMin t' in Node t (tDelete (tMin t') t') fMin
My main concerns are:
- The balancing algorithm. I thought it would work beautifully at first, then I realized that it basically just turns the tree into a "V". It's more efficient then a linked list, but still not very balanced
- The 2 "tToList*" functions. Should I use foldl or foldr? They seem to act fairly equivalently; although foldl is easier to use because you typically read a list from the left
- The "tDelete" function. It works (from my testing), but it looks very ugly. I basically just wrote it case-by-case, which made it very long.