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

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 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 :)