Hello
I remember to have read a long time ago (I think it was at "Algorithms + Data Structures = Programs"), that to build and mantain an AVL tree is very costly. At the beginning, to build the data structures necessary while a compiler is compiling a program (to store the variables, the staments, etc.), they used an AVL tree. But then they found that it is more eficient to build a natural tree (you just insert the new elements as they are coming, without reorganizing the rest of the elements). Using statistical studies, they found that at the average the natural trees are normally enough good; the worst cases (for example a degenerated tree or list) are rare; and it was preferable that the compiling of a particular rare program (one that produces a bad tree) will consume more time, that to penalize the compiling of ALL programs using and optimal AVL tree.
So perhaps you should valorate if an AVL tree is really necessary.
Regards,
Manuel
> Date: Sat, 3 Sep 2011 10:16:28 +0100
> From: robert.campbell_{([at]})nowhere.xy
> Subject: [BLACKBOX] AVL Trees
> To: BLACKBOX{([at]})nowhere.xy>
> Hiya
>
> Has anyone published an AVL-Tree module (preferably with some documentation)?
>
> I thought there was a good example in "Modula-2" by John Beidler & Paul
> Jackowitz, but after translating their code (which was easy!) I realised that it
> only included insertion, and other operations such as deletion were actually
> even more tricky!
>
> Cheers
>
> Robert
>
>
> ----
> To unsubscribe, send a message with body "SIGNOFF BLACKBOX" to LISTSERV{([at]})nowhere.xy---- To unsubscribe, send a message with body "SIGNOFF BLACKBOX" to LISTSERV{([at]})nowhere.xy
Received on Mon Sep 05 2011 - 11:38:59 UTC