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

[Achim Schneider]

PR Stanley <prstanley at ntlworld.com> 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 at ntlworld.com> 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 at 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.