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@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[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@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[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 <prstanley@...> 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@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

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

[Achim Schneider]

PR Stanley <prstanley@...> 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?
>
Using a library ;)

Inserting isn't the problem, balancing is where things get interesting:
have a look at

http://en.wikipedia.org/wiki/AVL_tree

--
(c) this sig last receiving data processing entity. Inspect headers for
past copyright information. All rights reserved. Unauthorised copying,
hiring, renting, public performance and/or broadcasting of this
signature prohibited.

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

[PR Stanley]

Actually, you've touched an important point there. It's balancing
that I'm having difficulty with.
Paul
At 23:46 09/05/2008, you wrote:

>PR Stanley <prstanley@...> 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?
> >
>Using a library ;)
>
>Inserting isn't the problem, balancing is where things get interesting:
>have a look at
>
>http://en.wikipedia.org/wiki/AVL_tree
>
>--
>(c) this sig last receiving data processing entity. Inspect headers for
>past copyright information. All rights reserved. Unauthorised copying,
>hiring, renting, public performance and/or broadcasting of this
>signature prohibited.
>
>_______________________________________________
>Haskell-Cafe mailing list
>Haskell-Cafe@...
>http://www.haskell.org/mailman/listinfo/haskell-cafe

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

[PR Stanley]

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

         Paul: The idea is to find a value in the tree greater than
the new value and then placing the new value before it on the tree.
duplicates are ignored and if no value greater than he new value is
found then it is appended as a new node to the end of the last node checked.
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.
Cheers
Paul

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

[Bulat Ziganshin-2]

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 | x<y  =  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,
 Bulat                            mailto:Bulat.Ziganshin@...

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

[Tomas Andersson]

Den Saturday 10 May 2008 00.55.44 skrev PR Stanley:
> Actually, you've touched an important point there. It's balancing
> that I'm having difficulty with.
> Paul
>

 So what kind of balancing rules does it have to obey? AVL? Red-black?
Something else?

> At 23:46 09/05/2008, you wrote:
> >PR Stanley <prstanley@...> 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?
> >
> >Using a library ;)
> >
> >Inserting isn't the problem, balancing is where things get interesting:
> >have a look at
> >
> >http://en.wikipedia.org/wiki/AVL_tree
> >
> >--
> >(c) this sig last receiving data processing entity. Inspect headers for
> >past copyright information. All rights reserved. Unauthorised copying,
> >hiring, renting, public performance and/or broadcasting of this
> >signature prohibited.
> >
> >_______________________________________________
> >Haskell-Cafe mailing list
> >Haskell-Cafe@...
> >http://www.haskell.org/mailman/listinfo/haskell-cafe
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@...
> http://www.haskell.org/mailman/listinfo/haskell-cafe

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

[Achim Schneider]

PR Stanley <prstanley@...> wrote:

> Actually, you've touched an important point there. It's balancing
> that I'm having difficulty with.
> Paul

http://en.wikipedia.org/wiki/Tree_rotation is the key to all this: It
changes the tree structure without changing the tree ordering.

rotr (Node (Node a p b) q c) = Node a p $ Node b q c

untested, mind you.

> At 23:46 09/05/2008, you wrote:
> >PR Stanley <prstanley@...> 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?
> > >
> >Using a library ;)
> >
> >Inserting isn't the problem, balancing is where things get
> >interesting: have a look at
> >
> >http://en.wikipedia.org/wiki/AVL_tree
> >
> >--
> >(c) this sig last receiving data processing entity. Inspect headers
> >for past copyright information. All rights reserved. Unauthorised
> >copying, hiring, renting, public performance and/or broadcasting of
> >this signature prohibited.
> >
> >_______________________________________________
> >Haskell-Cafe mailing list
> >Haskell-Cafe@...
> >http://www.haskell.org/mailman/listinfo/haskell-cafe

--
(c) this sig last receiving data processing entity. Inspect headers for
past copyright information. All rights reserved. Unauthorised copying,
hiring, renting, public performance and/or broadcasting of this
signature prohibited.

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