3 ms·
You can sort a linked list in O(nlog(n)) time with O(log(n)) space, and then convert it to a balanced binary tree in O(nlog(n)) time and O(log(n)) space. EDIT:
by pklausler 9y ago
You can sort a linked list in O(nlog(n)) time with O(log(n)) space, and then convert it to a balanced binary tree in O(nlog(n)) time and O(log(n)) space.
EDIT: demonstration:
sortList [] = []
sortList [x] = [x]
sortList xs = merge (sortList as) (sortList bs)
where
(as, bs) = split xs
split [] = ([], [])
split [x] = ([x], [])
split (x:y:rest) = let (xs, ys) = split rest in (x:xs, y:ys)
merge xs [] = xs
merge [] ys = ys
merge (x:xs') ys@(y:_) | x <= y = x : merge xs' ys
merge xs (y:ys) = y : merge xs ys
data Tree a = Empty | Node a (Tree a) (Tree a) deriving(Show)
balancedTree xs = mktree (length xs) xs
where
mktree 0 [] = Empty
mktree n xs = Node x (mktree n' less) (mktree (n - 1 - n') more)
where
n' = (n - 1) `div` 2
(less, (x:more)) = splitAt n' xs
listToBalancedTree :: Ord a => [a] -> Tree a
listToBalancedTree = balancedTree . sortList