[Haskell-beginners] [Fwd: Binary tree algorithm]

[Daniel Fischer]

On Thursday 06 May 2010 21:51:47, legajid wrote:
> Oops, mistake in sender name.
>
> Hi,
> i wanted to write an algorithm for loading a binary tree, then get the
> values in order and other operations.
>
> So, i created a data type :
> data AR a = R a (AR a) (AR a) | N   deriving (Show, Ord, Eq)
> for an example : R 30 (R 10 (N) (R 20 N N )) (R 40 (N) (R 50 N N ))
>
> the main problem i had is : how to update such a complex value, to add
> another one.

insert :: Ord a => a -> AR a -> AR a
insert x ar@(R y l r)
    | x < y     = R y (insert x l) r
    | x == y    = ar
    | otherwise = R y l (insert x r)
insert x N = R x N N

However, this might lead to very skewed trees. In general it is preferable 
to use balanced trees to prevent that. Then you would store the size (or 
the depth) in the nodes alongside the data and rebalance the tree when it 
becomes too skewed. There are packages for trees on Hackage, also you could 
look at the implementation of Data.Set for deeper insights.

> After hours of trying (and error !) my solution is : find where to
> insert the new value, then read the whole tree and copy its values,
> except for the one for insert.
> The tree must be read entirely as long as there are values to insert.
> For large numbers of values, i guess calculation time will increase
> seriously.

If you don't balance the tree, you risk that its depth (and hence an 
insert) is O(size), making the building of a tree of size n an O(n^2) 
algorithm [okay, that is the worst case, when the list of items to insert 
is basically sorted; more often it would be a depth of O(n^0.5) or so].

With a balanced tree, the depth is O(log size), making the building an 
O(n*log n) algorithm.

Also, for efficiency, you should make the tree strict (at least the 
structure),

data AR a = R a !(AR a) !(Ar a)

>
> I wrote it using "basic" Haskell capabilities. Are there some modules
> that manage this in a quicker way?

Search Hackage for "tree", look at Data.Set.

> using mutable variables ?
>
> Below is my code. How can it be improved ?
> Several limitations to my program (i could solve them) :
> . only Int values (strings should not be a problem)
> . minimum 2  values to make a tree
> . no duplicate values :it's used to find the node where to insert a new
> value. To allow duplicates, i should generate a unique "node id".
>
> -- cre [30, 10, 40, 50, 20]
> cre :: [Int] -> AR Int
> cre val =
>    -- add values except the first one
>    cre' (tail val) arb
>    where
>        -- init tree with first value
>        arb=R (head val) N N
>
> -- Add values to the tree
> cre' :: [Int] -> AR Int -> AR Int
> cre' [] arb = arb    -- at the end, get last value for the tree data
> cre' (x:xs) arb =
>    cre' xs (cre'' x arb)
>
> -- Find the node where to insert the new value and proceed
> cre'' :: Int -> AR Int -> AR Int
> cre'' n arb =
>    cre''' n arb (r, gd)
>    where
>        (r, gd)= trouve n arb -- insert at node value r, g(auche) ou
> d(roite)
>
> --  Read the whole tree and update the specified node to insert the new
> value
> cre''' :: Int -> AR Int -> (Int, String) -> AR Int
> cre''' _ N _ = N
> cre''' n (R x y z) (r, gd) =
>    R x (cre''' n y' (r,gd)) (cre''' n z' (r,gd))
>    where
>        -- left value (<)
>        y' = if x == r && gd=="g" then R n N N
>                          else y
>        -- right value (>)
>        z' = if x == r && gd=="d" then R n N N
>                          else z
>
> -- find the node where to insert the value
> trouve :: Int -> AR Int -> (Int, String)
> trouve n (R x y z)
>
>    | n <= x && y == N    =  (x, "g")
>    | n <= x        = trouve n y
>    | n > x && z == N    =  (x, "d")
>    | n > x            = trouve n z
>
> trouve n (N) = (0, " ")
>
> Thanks for your comments and help.
>
> Didier.