Building a Tree from an Ordered List

31/03/2009

A nice recursive algorithm for building a nearly-optimal binary search tree from an ordered list.:

data Tree a = Node a (Tree a) (Tree a)
            | End

The algorithm divides the input list into sublists of increasing length: 1,2,4,8… The first element of each sublist is the “keystone” of a subtree assembled with mkTree. :

fromSorted :: [a] -> Tree a
fromSorted = foldl mkTree End . divide 1
    where mkTree l (n:ns) = Node n l (fromSorted ns)
          divide _ [] = []
          divide c xs = take c xs : divide (c*2) (drop c xs)

Variations that used splitAt instead of the separate take and drop were no more efficient (perhaps because of sharing?) nor was using the strict foldl'.

Anyone have a clever alternative to the divide function defined here? Or a different approach to the problem? Would love to hear it.

There are 7 comments in this article:

  1. 1/04/2009Dan Doel says:

    This is probably not as fast, but I was thinking a bit about how to build optimal trees from sorted lists not too long ago, and thought this would be a good opportunity to write it down:

    import Control.Arrow
    import Control.Monad.State

    import Data.List

    data Tree a = Node (Tree a) a (Tree a)
    | End

    data Nat = Z | S Nat deriving (Show, Eq)

    instance Num Nat where
    fromInteger 0 = Z
    fromInteger n = S (fromInteger $ n – 1)
    Z + n = n
    S m + n = S (m + n)
    Z * _ = Z
    S m * n = n + m * n
    abs n = n
    negate n = error “Can’t negate a natural.”
    signum n = n

    slice :: Nat -> (Nat, Nat)
    slice Z = (Z, Z)
    slice (S n) = S . snd &&& fst <<< slice $ n

    pick :: State [a] a
    pick = do (e:es) Tree a
    fromSorted l = evalState (build $ genericLength l) l
    where
    build Z = return End
    build (S n) = Node `liftM` build l `ap` pick `ap` build r
    where (l, r) = slice n

    – snip –

    This divides elements as equally as possible amongst subtrees. I’ve not done any work optimizing anything. It’s conceivable that the natural numbers are a mistake, and it’s better to just bite the bullet and use Ints, length and divMod.

    Sorry if this is messy. I don’t know how to mark up code here.

  2. 1/04/2009admin says:

    Dan, thanks for sharing. I’ll have to look closer at that. I’m still figuring out the blog thing; maybe I can figure out how to let people format code. Does the pre tag work?…

    code

  3. 1/04/2009Brian Hurt says:

    I’d recommend reading:

    http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.2171

    Gives a real nice algorithm for building balanced trees from sorted lists of elements in O(N). The paper is talking about red-black trees, but there is nothing in the algorithm that really depends upon the balancing mechanism being anything particular, I’ve implemented it for height and weight balanced trees as well, and for descending as well as ascending lists.

  4. 1/04/2009admin says:

    Brian, thanks! That paper looks very readable and interesting. I found it here.

  5. 1/04/2009josh says:

    I don’t know if it’s any better, but I certainly think this is more clever:

    divide xs = let (parts, rest) = unzip . zipWith splitAt (iterate (*2) 1) . takeWhile (not . null) $ xs:rest in parts

  6. 3/04/2009jberryman says:

    josh, I played with trying to come up with something like that for a good long time, but couldn’t quite get it. Thanks!

  7. 14/08/2009Module for grouping lists in Haskell | LAMBDAPHONE says:

    [...] is an example from a previous post to build a binary tree from an in-order list, which uses the above [...]

Write a comment: