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! -- View this message in context: http://www.nabble.com/I-need-help-on-AVL-trees-tf3657386.html#a10218190 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
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
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... 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... Regards -- Adrian Hey
participants (3)
-
Adrian Hey -
iliali16 -
Stefan O'Rear