Re: [BLACKBOX] AVL Trees

From: Campbell, Robert (SELEX GALILEO, UK) <robert.d.campbell{([at]})nowhere.xy>
Date: Mon, 5 Sep 2011 10:03:50 +0100

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

Bob

Thanks for the reference (why didn't I look there first?)

In section 4.5.2, in procedure "balanceR", there is an assignment "b2 :p2.bal;".

b2 is neither declared or used, and this assigment is not in the mirror
procedure "balanceR". I guess that
it is there by error, and should simply be omitted. When I do that the
procedure seems to work.

Is there another version of the book (Pascal or Modula-II) on the web so
I can check what they say?



Wirth also says "It is indeed difficult to beat the straighforward,
simple tree insertion algorithm". I am inclined to agree.
The complexity of AVL trees may be an optimisation beyond what I
currently need, but interesting all the same.


Thanks

Robert


 

>> -----Original Message-----
>> From: BlackBox [mailto:BLACKBOX{([at]})nowhere.xy
>> Of Bob Walkden
>> Sent: 03 September 2011 10:21
>> To: BLACKBOX{([at]})nowhere.xy
>> Subject: Re: [BLACKBOX] AVL Trees
>>
>> *** WARNING ***
>>
>> This message has originated outside your organisation,
>> either from an external partner or the Global Internet.
>> Keep this in mind if you answer this message.
>>
>>
>> My edition of Wirth's Algorithms & Data Structures includes
>> an example which shows insertion and deletion. It's a
>> Modula-2 version.
>>
>> There's an Oberon version here (pdf download):
>> <http://www.ethoberon.ethz.ch/WirthPubl/AD.pdf>
>>
>> The AVL algorithms are in section 4.5ff.
>>
>> B
>>
>> > -----Original Message-----
>> > From: BlackBox [mailto:BLACKBOX{([at]})nowhere.xy
>> Of Robert
>> > Sent: 03 September 2011 10:16
>> > To: BLACKBOX{([at]})nowhere.xy
>> > Subject: [BLACKBOX] AVL Trees
>> >
>> > 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
>>
SELEX Galileo Ltd
Registered Office: Sigma House, Christopher Martin Road, Basildon, Essex SS14 3EL
A company registered in England & Wales. Company no. 02426132
********************************************************************
This email and any attachments are confidential to the intended
recipient and may also be privileged. If you are not the intended
recipient please delete it from your system and notify the sender.
You should not copy it or use it for any purpose nor disclose or
distribute its contents to any other person.
********************************************************************

----
To unsubscribe, send a message with body "SIGNOFF BLACKBOX" to LISTSERV{([at]})nowhere.xy----boundary-LibPST-iamunique-367555595_-_-
Content-type: application/rtf
Content-transfer-encoding: base64
Content-Disposition: attachment; filename="rtf-body.rtf"
e1xydGYxXGFuc2lcYW5zaWNwZzEyNTJcZnJvbXRleHQgXGRlZmYwe1xmb250dGJsDQp7XGYwXGZz
d2lzcyBBcmlhbDt9DQp7XGYxXGZtb2Rlcm4gQ291cmllciBOZXc7fQ0Ke1xmMlxmbmlsXGZjaGFy
c2V0MiBTeW1ib2w7fQ0Ke1xmM1xmbW9kZXJuXGZjaGFyc2V0MCBDb3VyaWVyIE5ldzt9fQ0Ke1xj
b2xvcnRibFxyZWQwXGdyZWVuMFxibHVlMDtccmVkMFxncmVlbjBcYmx1ZTI1NTt9DQpcdWMxXHBh
cmRccGxhaW5cZGVmdGFiMzYwIFxmMFxmczIwIEJvYlxwYXINClxwYXINClRoYW5rcyBmb3IgdGhl
IHJlZmVyZW5jZSAod2h5IGRpZG4ndCBJIGxvb2sgdGhlcmUgZmlyc3Q/KVxwYXINClxwYXINCklu
IHNlY3Rpb24gNC41LjIsIGluIHByb2NlZHVyZSAiYmFsYW5jZVIiLCB0aGVyZSBpcyBhbiBhc3Np
Z25tZW50ICJiMiA6PVxwYXINCnAyLmJhbDsiLlxwYXINClxwYXINCmIyIGlzIG5laXRoZXIgZGVj
bGFyZWQgb3IgdXNlZCwgYW5kIHRoaXMgYXNzaWdtZW50IGlzIG5vdCBpbiB0aGUgbWlycm9yXHBh
cg0KcHJvY2VkdXJlICJiYWxhbmNlUiIuIEkgZ3Vlc3MgdGhhdFxwYXINCml0IGlzIHRoZXJlIGJ5
IGVycm9yLCBhbmQgc2hvdWxkIHNpbXBseSBiZSBvbWl0dGVkLiBXaGVuIEkgZG8gdGhhdCB0aGVc
cGFyDQpwcm9jZWR1cmUgc2VlbXMgdG8gd29yay5ccGFyDQpccGFyDQpJcyB0aGVyZSBhbm90aGVy
IHZlcnNpb24gb2YgdGhlIGJvb2sgKFBhc2NhbCBvciBNb2R1bGEtSUkpIG9uIHRoZSB3ZWIgc29c
cGFyDQpJIGNhbiBjaGVjayB3aGF0IHRoZXkgc2F5P1xwYXINClxwYXINClxwYXINClxwYXINCldp
cnRoIGFsc28gc2F5cyAiSXQgaXMgaW5kZWVkIGRpZmZpY3VsdCB0byBiZWF0IHRoZSBzdHJhaWdo
Zm9yd2FyZCxccGFyDQpzaW1wbGUgdHJlZSBpbnNlcnRpb24gYWxnb3JpdGhtIi4gSSBhbSBpbmNs
aW5lZCB0byBhZ3JlZS5ccGFyDQpUaGUgY29tcGxleGl0eSBvZiBBVkwgdHJlZXMgbWF5IGJlIGFu
IG9wdGltaXNhdGlvbiBiZXlvbmQgd2hhdCBJXHBhcg0KY3VycmVudGx5IG5lZWQsIGJ1dCBpbnRl
cmVzdGluZyBhbGwgdGhlIHNhbWUuXHBhcg0KXHBhcg0KXHBhcg0KVGhhbmtzXHBhcg0KXHBhcg0K
Um9iZXJ0XHBhcg0KXHBhcg0KXHBhcg0KIFxwYXINClxwYXINCj4+IC0tLS0tT3JpZ2luYWwgTWVz
c2FnZS0tLS0tXHBhcg0KPj4gRnJvbTogQmxhY2tCb3ggW21haWx0bzpCTEFDS0JPWEBMSVNUUy5P
QkVST04uQ0hdIE9uIEJlaGFsZiBccGFyDQo+PiBPZiBCb2IgV2Fsa2RlblxwYXINCj4+IFNlbnQ6
IDAzIFNlcHRlbWJlciAyMDExIDEwOjIxXHBhcg0KPj4gVG86IEJMQUNLQk9YQExJU1RTLk9CRVJP
Ti5DSFxwYXINCj4+IFN1YmplY3Q6IFJlOiBbQkxBQ0tCT1hdIEFWTCBUcmVlc1xwYXINCj4+IFxw
YXINCj4+ICAgICAgICAgICAgICAgICAgICAgKioqIFdBUk5JTkcgKioqXHBhcg0KPj4gXHBhcg0K
Pj4gIFRoaXMgbWVzc2FnZSBoYXMgb3JpZ2luYXRlZCBvdXRzaWRlIHlvdXIgb3JnYW5pc2F0aW9u
LFxwYXINCj4+ICAgZWl0aGVyIGZyb20gYW4gZXh0ZXJuYWwgcGFydG5lciBvciB0aGUgR2xvYmFs
IEludGVybmV0LiBccGFyDQo+PiAgICAgICBLZWVwIHRoaXMgaW4gbWluZCBpZiB5b3UgYW5zd2Vy
IHRoaXMgbWVzc2FnZS5ccGFyDQo+PiAgXHBhcg0KPj4gXHBhcg0KPj4gTXkgZWRpdGlvbiBvZiBX
aXJ0aCdzIEFsZ29yaXRobXMgJiBEYXRhIFN0cnVjdHVyZXMgaW5jbHVkZXMgXHBhcg0KPj4gYW4g
ZXhhbXBsZSB3aGljaCBzaG93cyBpbnNlcnRpb24gYW5kIGRlbGV0aW9uLiBJdCdzIGEgXHBhcg0K
Pj4gTW9kdWxhLTIgdmVyc2lvbi4gXHBhcg0KPj4gXHBhcg0KPj4gVGhlcmUncyBhbiBPYmVyb24g
dmVyc2lvbiBoZXJlIChwZGYgZG93bmxvYWQpOlxwYXINCj4+IDxodHRwOi8vd3d3LmV0aG9iZXJv
bi5ldGh6LmNoL1dpcnRoUHVibC9BRC5wZGY+XHBhcg0KPj4gXHBhcg0KPj4gVGhlIEFWTCBhbGdv
cml0aG1zIGFyZSBpbiBzZWN0aW9uIDQuNWZmLlxwYXINCj4+IFxwYXINCj4+IEJccGFyDQo+PiBc
cGFyDQo+PiA+IC0tLS0tT3JpZ2luYWwgTWVzc2FnZS0tLS0tXHBhcg0KPj4gPiBGcm9tOiBCbGFj
a0JveCBbbWFpbHRvOkJMQUNLQk9YQExJU1RTLk9CRVJPTi5DSF0gT24gQmVoYWxmIFxwYXINCj4+
IE9mIFJvYmVydFxwYXINCj4+ID4gU2VudDogMDMgU2VwdGVtYmVyIDIwMTEgMTA6MTZccGFyDQo+
PiA+IFRvOiBCTEFDS0JPWEBMSVNUUy5PQkVST04uQ0hccGFyDQo+PiA+IFN1YmplY3Q6IFtCTEFD
S0JPWF0gQVZMIFRyZWVzXHBhcg0KPj4gPiBccGFyDQo+PiA+IEhpeWFccGFyDQo+PiA+IFxwYXIN
Cj4+ID4gSGFzIGFueW9uZSBwdWJsaXNoZWQgYW4gQVZMLVRyZWUgbW9kdWxlIChwcmVmZXJhYmx5
IHdpdGggc29tZVxwYXINCj4+ID4gZG9jdW1lbnRhdGlvbik/XHBhcg0KPj4gPiBccGFyDQo+PiA+
IEkgdGhvdWdodCB0aGVyZSB3YXMgYSBnb29kIGV4YW1wbGUgaW4gIk1vZHVsYS0yIiBieSBKb2hu
IFxwYXINCj4+IEJlaWRsZXIgJiBQYXVsXHBhcg0KPj4gPiBKYWNrb3dpdHosIGJ1dCBhZnRlciB0
cmFuc2xhdGluZyB0aGVpciBjb2RlICh3aGljaCB3YXMgZWFzeSEpIElccGFyDQo+PiA+IHJlYWxp
c2VkIHRoYXQgaXRccGFyDQo+PiA+IG9ubHkgaW5jbHVkZWQgaW5zZXJ0aW9uLCBhbmQgb3RoZXIg
b3BlcmF0aW9ucyBzdWNoIGFzIGRlbGV0aW9uIHdlcmVccGFyDQo+PiA+IGFjdHVhbGx5XHBhcg0K
Pj4gPiBldmVuIG1vcmUgdHJpY2t5IVxwYXINCj4+ID4gXHBhcg0KPj4gPiBDaGVlcnNccGFyDQo+
PiA+IFxwYXINCj4+ID4gUm9iZXJ0XHBhcg0KPj4gPiBccGFyDQo+PiA+IFxwYXINCj4+ID4gLS0t
LVxwYXINCj4+ID4gVG8gdW5zdWJzY3JpYmUsIHNlbmQgYSBtZXNzYWdlIHdpdGggYm9keSAiU0lH
Tk9GRiBCTEFDS0JPWCIgdG9ccGFyDQo+PiA+IExJU1RTRVJWQExJU1RTLk9CRVJPTi5DSFxwYXIN
Cj4+IFxwYXINCj4+IFxwYXINCj4+IC0tLS1ccGFyDQo+PiBUbyB1bnN1YnNjcmliZSwgc2VuZCBh
IG1lc3NhZ2Ugd2l0aCBib2R5ICJTSUdOT0ZGIEJMQUNLQk9YIiBccGFyDQo+PiB0byBMSVNUU0VS
VkBMSVNUUy5PQkVST04uQ0hccGFyDQo+PiBccGFyDQpTRUxFWCBHYWxpbGVvIEx0ZFxwYXINClJl
Z2lzdGVyZWQgT2ZmaWNlOiBTaWdtYSBIb3VzZSwgQ2hyaXN0b3BoZXIgTWFydGluIFJvYWQsIEJh
c2lsZG9uLCBFc3NleCBTUzE0IDNFTFxwYXINCkEgY29tcGFueSByZWdpc3RlcmVkIGluIEVuZ2xh
bmQgJiBXYWxlcy4gIENvbXBhbnkgbm8uIDAyNDI2MTMyXHBhcg0KKioqKioqKioqKioqKioqKioq
KioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKipccGFyDQpU
aGlzIGVtYWlsIGFuZCBhbnkgYXR0YWNobWVudHMgYXJlIGNvbmZpZGVudGlhbCB0byB0aGUgaW50
ZW5kZWRccGFyDQpyZWNpcGllbnQgYW5kIG1heSBhbHNvIGJlIHByaXZpbGVnZWQuIElmIHlvdSBh
cmUgbm90IHRoZSBpbnRlbmRlZFxwYXINCnJlY2lwaWVudCBwbGVhc2UgZGVsZXRlIGl0IGZyb20g
eW91ciBzeXN0ZW0gYW5kIG5vdGlmeSB0aGUgc2VuZGVyLlxwYXINCllvdSBzaG91bGQgbm90IGNv
cHkgaXQgb3IgdXNlIGl0IGZvciBhbnkgcHVycG9zZSBub3IgZGlzY2xvc2Ugb3JccGFyDQpkaXN0
cmlidXRlIGl0cyBjb250ZW50cyB0byBhbnkgb3RoZXIgcGVyc29uLlxwYXINCioqKioqKioqKioq
KioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioq
XHBhcg0KXHBhcg0KXHBhcg0KLS0tLVxwYXINClRvIHVuc3Vic2NyaWJlLCBzZW5kIGEgbWVzc2Fn
ZSB3aXRoIGJvZHkgIlNJR05PRkYgQkxBQ0tCT1giIHRvIExJU1RTRVJWQExJU1RTLk99fQAgMuDA
QVJOSU5HZBI
----boundary-LibPST-iamunique-367555595_-_---

Received on Mon Sep 05 2011 - 11:03:50 UTC