[Haskell-beginners] [Fwd: Binary tree algorithm]
legajid at free.fr
Fri May 7 16:12:10 EDT 2010
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 ?
David Virebayre a écrit :
> On Thu, May 6, 2010 at 9:51 PM, legajid <legajid at free.fr> wrote:
>> 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.
> 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 :)
More information about the Beginners