[Haskell-beginners] [Fwd: Binary tree algorithm]
dav.vire+haskell at gmail.com
Thu May 6 16:37:57 EDT 2010
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