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

legajid legajid at free.fr
Thu May 6 15:51:47 EDT 2010

Oops, mistake in sender name.

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.
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 

I wrote it using "basic" Haskell capabilities. Are there some modules 
that manage this in a quicker way?  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
       -- 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)
       (r, gd)= trouve n arb -- insert at node value r, g(auche) ou 

--  Read the whole tree and update the specified node to insert the new 
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))
       -- 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.


More information about the Beginners mailing list