[Haskell-cafe] I need help on AVL trees

Adrian Hey ahey at iee.org
Sat Apr 28 02:37:33 EDT 2007


Stefan O'Rear wrote:
> On Fri, Apr 27, 2007 at 05:27:37AM -0700, iliali16 wrote:
>> Can someone advise me how can I build an AVL tree becouse I have difficulties
>> with the rotations. Since if I add a node I want to be abel to check whether
>> the tree is balanced or not if balanced ok but if not I need to do one of
>> the 4 rotations which is a problem for me and I want to be able to give the
>> nodes from the keyboard. What I mean is that it is possible to build the
>> tree from scratch. Thanks to all!
> 
> If you just want a balanced tree, check out Data.Map, which is in the
> standard library so you don't need to figure out how to write it. 
> 
> http://haskell.org/ghc/dist/current/docs/libraries/base/Data-Map.html

I believe the OP was asking about AVL trees, not maps in general.

Also Data.Map isn't standard actually :-)

I'm not sure what the question really is and I feel disinclined to
answer it anyway 'cos it seems like homework to me. But if iliali16
wants some help re. AVL balancing rotations then the ASCII art
in this module might be of use..

http://darcs.haskell.org/packages/collections-ghc6.6/Data.Tree.AVL/Data/Tree/AVL/Push.hs

This crib sheet tells how to determine the change in height from
change in balance factor..

http://darcs.haskell.org/packages/collections-ghc6.6/Data.Tree.AVL/Data/Tree/AVL/MasterTable.KeepMe.txt


Regards
--
Adrian Hey




More information about the Haskell-Cafe mailing list