Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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.
share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.