Re: [BLACKBOX] AVL Trees

From: [at]} <Robert>
Date: Tue, 6 Sep 2011 20:39:02 +0100

----boundary-LibPST-iamunique-409247175_-_-
Content-type: text/plain

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----boundary-LibPST-iamunique-409247175_-_-
Content-type: application/rtf
Content-transfer-encoding: base64
Content-Disposition: attachment; filename="rtf-body.rtf"
e1xydGYxXGFuc2lcYW5zaWNwZzEyNTJcZnJvbXRleHQgXGRlZmYwe1xmb250dGJsDQp7XGYwXGZz
d2lzcyBBcmlhbDt9DQp7XGYxXGZtb2Rlcm4gQ291cmllciBOZXc7fQ0Ke1xmMlxmbmlsXGZjaGFy
c2V0MiBTeW1ib2w7fQ0Ke1xmM1xmbW9kZXJuXGZjaGFyc2V0MCBDb3VyaWVyIE5ldzt9fQ0Ke1xj
b2xvcnRibFxyZWQwXGdyZWVuMFxibHVlMDtccmVkMFxncmVlbjBcYmx1ZTI1NTt9DQpcdWMxXHBh
cmRccGxhaW5cZGVmdGFiMzYwIFxmMFxmczIwIEZ5b2RvclxwYXINClxwYXINClRoYW5rcyBmb3Ig
eW91ciBhdHRhY2htZW50LlxwYXINClxwYXINClRoZSBBVkxfVHJlZSBjb2RlIGlzIHRoZSBzYW1l
IGFzIHRoYXQgaW5ccGFyDQo8aHR0cDovL3d3dy5ldGhvYmVyb24uZXRoei5jaC9XaXJ0aFB1Ymwv
QUQucGRmPixccGFyDQpleGNlcHQgdGhhdCB0aGUgbWlub3IgJ2Vycm9yJyBJIG1lbnRpb25lZCBp
biBhIHByZXZpb3VzIHBvc3QgaGFzIGJlZW4gY29ycmVjdGVkLlxwYXINClxwYXINClxwYXINCkkg
c3RpbGwgaGF2ZSBhIHByb2JsZW0gd2l0aCB0aGUgcm91dGluZSAnZGVsZXRlJy4gSXQgaXMgY2Fs
bGVkIHdpdGggYSBCT09MRUFOIFxwYXINClZBUiBwYXJhbWV0ZXIgaC4gSSBkbyBub3Qga25vdyBp
ZiBoIHNob3VsZCBiZSBzZXQgdG8gVFJVRSBvciBGQUxTRSBmaXJzdCwgb3IgXHBhcg0KanVzdCBs
ZWZ0IHVuZGVmaW5lZC5ccGFyDQpccGFyDQpJIGhhdmUgZG9uZSBhIGZldyBleHBlcmltZW50cywg
YW5kIGl0cyB2YWx1ZSBkb2VzIG5vdCBzZWVtIHRvIG1hdHRlci4gQnV0IEkgaGF2ZSBccGFyDQpu
b3QgdG90YWxseSBjb252aW5jZWQgbXlzZWxmIHRoYXQgaXMgY29ycmVjdCAtIEFWTCBUcmVlcyBh
cmUgcXVpdGUgZGlmZmljdWx0IVxwYXINClxwYXINClxwYXINCllvdXIgY29kZSBjb250YWlucyBh
biBleGFtcGxlIHJvdXRpbmUgJ0RlbGV0ZScgdGhhdCB1c2VzICdkZWxldGUnLCBhbmQgaXQgYWxz
byBccGFyDQpsZWF2ZXMgaCB1bmRlZmluZWQgd2hpY2ggZ2l2ZXMgZnVydGhlciByZWFzb24gdG8g
YmVsaWV2ZSB0aGF0IGl0IGRvZXMgbm90IG1hdHRlci5ccGFyDQpccGFyDQpJdCB0aGF0IHJlYWxs
eSBpcyB0aGUgY2FzZSwgaXQgd291bGQgYmUgYW4gaW1wcm92ZW1lbnQgdG8gY2hhbmdlIHRoZSBy
b3V0aW5lIFxwYXINCnNpZ25hdHVyZSBmcm9tXHBhcg0KXHBhcg0KICAgUFJPQ0VEVVJFIGRlbGV0
ZSAoIHg6IElOVEVHRVI7ICBWQVIgcDogTm9kZTsgIFZBUiBoOiBCT09MRUFOICk7XHBhcg0KdG9c
cGFyDQogICBQUk9DRURVUkUgZGVsZXRlICggeDogSU5URUdFUjsgIFZBUiBwOiBOb2RlOyAgT1VU
IGg6IEJPT0xFQU4gKTtccGFyDQpccGFyDQp0byBtYWtlIGl0IGNsZWFyZXIgZm9yIG90aGVyIHBl
b3BsZS5ccGFyDQpccGFyDQpccGFyDQpXaXJ0aCdzIGJvb2sgbWlnaHQgc2F5IHRoYXQgaCBzaG91
bGQgYmUgcHJlc2V0IHRvIEZBTFNFIChidXQgSSBkb24ndCBmaW5kIGl0IFxwYXINCmNsZWFyKS4g
SWYgdGhhdCBpcyB0aGUgY2FzZSB5b3VyICdEZWxldGUnIGV4YW1wbGUgc2hvdWxkIGJlIGNvcnJl
Y3RlZC5ccGFyDQpccGFyDQpccGFyDQpccGFyDQpSZWdhcmRzXHBhcg0KXHBhcg0KUm9iZXJ0XHBh
cg0KXHBhcg0KXHBhcg0KT24gMDYvMDkvMjAxMSAwNDoyOCBQTSwgRnlvZG9yIFRrYWNob3Ygd3Jv
dGU6XHBhcg0KPj4gSGFzIGFueW9uZSBwdWJsaXNoZWQgYW4gQVZMLVRyZWUgbW9kdWxlIChwcmVm
ZXJhYmx5IHdpdGggc29tZSBkb2N1bWVudGF0aW9uKT9ccGFyDQo+XHBhcg0KPj4gSSB0aG91Z2h0
IHRoZXJlIHdhcyBhIGdvb2QgZXhhbXBsZSBpbiAiTW9kdWxhLTIiIGJ5IEpvaG4gQmVpZGxlciYg
IFBhdWxccGFyDQo+PiBKYWNrb3dpdHosIGJ1dCBhZnRlciB0cmFuc2xhdGluZyB0aGVpciBjb2Rl
ICh3aGljaCB3YXMgZWFzeSEpIEkgcmVhbGlzZWQgdGhhdCBpdFxwYXINCj4+IG9ubHkgaW5jbHVk
ZWQgaW5zZXJ0aW9uLCBhbmQgb3RoZXIgb3BlcmF0aW9ucyBzdWNoIGFzIGRlbGV0aW9uIHdlcmUg
YWN0dWFsbHlccGFyDQo+PiBldmVuIG1vcmUgdHJpY2t5IVxwYXINCj5ccGFyDQo+PiBDaGVlcnNc
cGFyDQo+PiBSb2JlcnRccGFyDQo+XHBhcg0KPlxwYXINCj4gSGVsbG8gUm9iZXJ0LFxwYXINCj5c
cGFyDQo+IEVuY29kZWQgaXMgdGhlIG1vZHVsZSBmcm9tIHRoZSBuZXcgUnVzc2lhbiB0cmFuc2xh
dGlvbiBvZiBBbGdvcml0aG1zIGFuZCBEYXRhIFN0cnVjdHVyZXMuXHBhcg0KPiBBY3R1YWxseSwg
aXQgaXMgdGhyZWUgbW9kdWxlcywgdG8gc2ltdWxhdGUgT2Jlcm9uJ3MgVGV4dHMuXHBhcg0KPlxw
YXINCj4gVGhlcmUgYXJlIHNvbWUgY29tbWVudHMgaW4gUnVzc2lhbiB0cmFuc2xhdGVkLCBzb21l
IHRyYW5zbGF0ZWQgZnJvbSB0aGUgb3JpZ2luYWwsIGFuZCBzb21lIG90aGVyIGFkZGVkLlxwYXIN
Cj5ccGFyDQo+IFRoZSBlbnRpcmUgc2V0IG9mIGV4YW1wbGVzIGZvciB0aGUgYm9vayBpcyBpbiB0
aGlzIGFyY2hpdmU6XHBhcg0KPiBodHRwOi8vd3d3Lmluci5hYy5ydS9+YmxhY2tib3gvcnNyYy9B
RHJ1LnppcFxwYXINCj4gUGxlYXNlIG5vdGUgdGhhdCB0aGUgc2VjdGlvbiBudW1iZXJpbmcgbWF5
IGRpZmZlciBmcm9tIHRoZSBFbmdsaXNoIG9yaWdpbmFsIG9uIE5pa2xhdXMncyB3ZWIgcGFnZS5c
cGFyDQo+XHBhcg0KPiBJdCBzaG91bGQgYmUgcnVuIG9uIHRvcCBvZiB0aGlzIGNvbmZpZ3VyYXRp
b24gb2YgQmxhY2tCb3g6XHBhcg0KPiBodHRwOi8vd3d3Lmluci5hYy5ydS9+YmxhY2tib3gvcnNy
Yy9ibGFja2JveDE1aTIxYmFzZS43elxwYXINCj5ccGFyDQo+IEkgcHJvbWlzZWQgdG8gTlcgdG8g
cmV0cm9maXQgdGhlIGNoYW5nZXMgbWFkZSB0byB0aGUgUnVzc2lhbiB0cmFuc2xhdGlvbiBpbnRv
IHRoZSBFbmdsaXNoIHRleHQgKHRoZSBjaGFuZ2VzIHdlcmUgYXBwcm92ZWQgYnkgTlcpLFxwYXIN
ClxwYXINCiAgYnV0IC0tIGFzIHlvdSBjb3JyZWN0bHkgc3VybWlzZWQgYXQgdGhlIE8nRGF5MjAx
MSwgSSBhbSBzb21ld2hhdCBwcmVzc2VkIGZvciBccGFyDQp0aW1lLi4uXHBhcg0KPlxwYXINCj4g
Y2hlZXJzXHBhcg0KPiBmeW9kb3JccGFyDQo+XHBhcg0KXHBhcg0KXHBhcg0KLS0tLVxwYXINClRv
IHVuc3Vic2NyaWJlLCBzZW5kIGEgbWVzc2FnZSB3aXRoIGJvZHkgIlNJR05PRkYgQkxBQ0tCT1gi
IHRvIExJU1RTRVJWQExJU1RTLk9CRVJPTi5DSFxwYXINCn0=
----boundary-LibPST-iamunique-409247175_-_---

Received on Tue Sep 06 2011 - 21:39:02 UTC