Tuesday, April 5, 2016

Generate BST for an ordered list

It seems hard when first heard of this. However, it's way more easier they I thought:

import Data.Array
import Data.List

data BTree a = Leaf | Branch a (BTree a) (BTree a) deriving Show

-- | the type signature can be omitted, use it here for documentation
makeBST :: Ord a => [a] -> BTree a
makeBST xs = acc (listArray (1, len) (sort xs)) 1 len
  where len = length xs
        acc u i j
          | i > j = Leaf
          | i <= j = Branch (u ! k) (acc u i (pred k)) (acc u (succ k) j)
            where k = (i+j) `div` 2

The idea is extremely simple, for a (sub) list already sorted, divide it to

  [left] ++ [pivot] ++ [right]

make pivot to be the root node, then call makeBST recursively on both @left and @right, and inserted it to the root node.

I've spotted C++ implementation which made me headache, however, the Haskell version feels like a one-liner.

Guess I've found another example of my theory:

  To learn algorithm, you probably shouldn't read any code at all, not even pseudo code.

There are some outstanding books on algorithms, what I don't like is the imperative style pseudo code, and assume you have to implement the algorithm with C/C++/Java, which is really hard to understand. To me, if I tried to read into the code, I would forget the algorithm itself pretty quick, 3 month later, I forget the code altogether; Instead, tried to understand the algorithm without any code (or at least functional ones, draw graphs if necessary). It may take longer when implement some algorithms than memorizing the code, the upside is this kind of memory last really long.

No comments:

Post a Comment