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

[legajid]

Hi,
much more simple and efficient than my solution.
I just see a strange thing. I changed < to <=, then > to >= in order to 
insert duplicate values, and added a top level function to give a list 
of values to insert.
with <=, inser [40,40,30,40,50] gives R 40 (R 40 (R 30 N (R 40 N N)) N) 
(R 50 N N)
with >=, inser [40,40,30,40,50] gives R 40 (R 30 N N) (R 40 N (R 40 N (R 
50 N N)))

Traversing the tree in ascending order from left to right, the  results 
are the same.
In the first case, left tree has a depth of three. In the second case, 
right tree does.
But are these different layouts totally equivalent?
I think that the depth of each branch is dependent upon the order of 
input data and the test (<=, >=). Can i evaluate this prior to loading 
the tree, so that i avoid having a tree with a branch much larger than 
the other one ?

Thanks,
Didier



David Virebayre a écrit :
> 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 :)
>
>