RE: AVL trees
Alan Freed implemented an AVL module in Zonnon; it is part of his BEL package:
http://www.zonnon.ethz.ch/usergroup/bel.html
Also, C. Lins published a nice 4 volume series entitled 'The Modula-2 Software Component Library'. Volume 3 has a good deal on AVL trees, and the sources could probably be translated without a great deal of difficultly (object differences notwithstanding). The source for this series can be obtained here:
http://www.aha.ru/~uranus/download.html.
-Mike
From: Robert <robert.campbell_{([at]})nowhere.xy
To: BLACKBOX{([at]})nowhere.xy
Sent: Tuesday, September 6, 2011 3:39 PM
Subject: Re: [BLACKBOX] AVL Trees
Fyodor
Thanks for your attachment.
The AVL_Tree code is the same as that in
<
http://www.ethoberon.ethz.ch/WirthPubl/AD.pdf>,
except that the minor 'error' I mentioned in a previous post has been corrected.
I still have a problem with the routine 'delete'. It is called with a BOOLEAN
VAR parameter h. I do not know if h should be set to TRUE or FALSE first, or
just left undefined.
I have done a few experiments, and its value does not seem to matter. But I have
not totally convinced myself that is correct - AVL Trees are quite difficult!
Your code contains an example routine 'Delete' that uses 'delete', and it also
leaves h undefined which gives further reason to believe that it does not matter.
It that really is the case, it would be an improvement to change the routine
signature from
PROCEDURE delete ( x: INTEGER; VAR p: Node; VAR h: BOOLEAN );
to
PROCEDURE delete ( x: INTEGER; VAR p: Node; OUT h: BOOLEAN );
to make it clearer for other people.
Wirth's book might say that h should be preset to FALSE (but I don't find it
clear). If that is the case your 'Delete' example should be corrected.
Regards
Robert
On 06/09/2011 04:28 PM, Fyodor Tkachov wrote:
>> 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
>
>
> Hello Robert,
>
> Encoded is the module from the new Russian translation of Algorithms and Data Structures.
> Actually, it is three modules, to simulate Oberon's Texts.
>
> There are some comments in Russian translated, some translated from the original, and some other added.
>
> The entire set of examples for the book is in this archive:
> http://www.inr.ac.ru/~blackbox/rsrc/ADru.zip
> Please note that the section numbering may differ from the English original on Niklaus's web page.
>
> It should be run on top of this configuration of BlackBox:
> http://www.inr.ac.ru/~blackbox/rsrc/blackbox15i21base.7z
>
> I promised to NW to retrofit the changes made to the Russian translation into the English text (the changes were approved by NW),
but -- as you correctly surmised at the O'Day2011, I am somewhat pressed for
time...
>
> cheers
> fyodor
>
----
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 Tue Sep 06 2011 - 22:09:17 UTC