inserting values in a binary tree

PR Stanley

9 May 2008 9 May '08

6:35 p.m.

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

Show replies by date

Thomas Davie

9 May 9 May

6:40 p.m.

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

Lennart Augustsson

6:43 p.m.

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

Achim Schneider

6:46 p.m.

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?

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.

PR Stanley

6:55 p.m.

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

Tomas Andersson

10 May 10 May

5:09 a.m.

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 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@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

Achim Schneider

6:07 a.m.

PR Stanley 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 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@haskell.org 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.

6220

Age (days ago)

6221

Last active (days ago)

List overview

Download

6 comments

5 participants

participants (5)

Achim Schneider
Lennart Augustsson
PR Stanley
Thomas Davie
Tomas Andersson