[Haskell-cafe] inserting values in a binary tree

[PR Stanley]

Hi
data Ord a = Tree a = Nil | Node (Tree a) a (Tree a)
How would one go about inserting a value in a binary search tree of 
the above description?


Cheers
Paul

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] inserting values in a binary tree

[Thomas Davie]

On 10 May 2008, at 00:35, PR Stanley wrote:


Hi
data Ord a = Tree a = Nil | Node (Tree a) a (Tree a)
How would one go about inserting a value in a binary search tree of  
the above description?


All you need to do is consider what the trees should look like in the  
two cases:


If I try and insert an item into a completely empty tree, what do I  
end up with?  I'll give you a hint, it has one Node, and 2 Nils.
If I have a Node, do I need to insert into the left tree, or the right  
tree?


Take it from there

Bob
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] inserting values in a binary tree

[Lennart Augustsson]

Are there any invariants you wish to maintain when inserting?  If not, it's
rather trivial.

  -- Lennart

On Fri, May 9, 2008 at 11:35 PM, PR Stanley [EMAIL PROTECTED] wrote:

 Hi
 data Ord a = Tree a = Nil | Node (Tree a) a (Tree a)
 How would one go about inserting a value in a binary search tree of the
 above description?

 Cheers
 Paul

 ___
 Haskell-Cafe mailing list
 Haskell-Cafe@haskell.org
 http://www.haskell.org/mailman/listinfo/haskell-cafe

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re[2]: [Haskell-cafe] inserting values in a binary tree

[Bulat Ziganshin]

Hello PR,

Saturday, May 10, 2008, 3:10:59 AM, you wrote:

 in C you'd fiddle with pointers and Bob's your uncle. Here I'm not
 sure how to piece that tree back together again with the new element 
 after having expanded it recursively.

in Haskell, you just return new tree with element inserted. it's
constructed from the two subtrees, where you've inserted element in
one of these. and so on recursively:

data Tree a = Tree a (Tree a) (Tree a)
| EmptyTree
insert (Tree x t1 t2) y | xy  =  Tree x t1 (insert t2 y)
insert (Tree x t1 t2) y=  Tree x (insert t1 y) t2
insert EmptyTree  y=  Tree y EmptyTree EmptyTree


-- 
Best regards,
 Bulatmailto:[EMAIL PROTECTED]

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe