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

[David Virebayre]

On Thu, May 6, 2010 at 9:51 PM, legajid <legajid at free.fr> 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.
> 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.


Let's say your tree is either empty or is a node that holds a value
and two subtrees, one for values that are smaller and one for values
that are greater.

What if you want to insert a value into an empty tree ?
You make a node with the given value and the two subtrees empty

ins v N = R v N N

what is the tree isn't empty ? two possibilities:
 - the value to insert is smaller than the node's value
   -> replace the subtree of smaller values by the result of
      inserting the value into that subtree
 - it's bigger

ins v (R v' s1 s2)
  | v < v' = R v' (ins v s1) s2
  | v > v' = R v' s1 (ins v s2)

question : what to do if v == v' ? I leave the question to you :)

That's it :)