Re: [BLACKBOX] AVL Trees

From: [at]} <Chris>
Date: Mon, 5 Sep 2011 22:33:50 +0930

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

>-----Original Message-----
>From: BlackBox [mailto:BLACKBOX{([at]})nowhere.xy
>Campbell, Robert (SELEX GALILEO, UK)
>Sent: Monday, 5 September 2011 6:34 PM
>To: BLACKBOX{([at]})nowhere.xy
>Subject: Re: [BLACKBOX] AVL Trees
>
>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?
>

Robert,

In the 1982 Modula-2 edition of the book, b2 was a local variable declared
as a subrange type:

  b1, b2: -1..+1;

The initial assignment was equivalent:

  b2 := p2^.bal;

and b2 was then used in the later statements. Instead of:

  IF p2.bal = -1 THEN p.bal := 1 ELSE p.bal := 0 END ;
  IF p2.bal = +1 THEN p1.bal := -1 ELSE p1.bal := 0 END ;

the equivalent statements were:

  IF b2 = -1 THEN p.bal := 1 ELSE p.bal := 0 END ;
  IF b2 = +1 THEN p1.bal := -1 ELSE p1.bal := 0 END ;

b1 was used similarly as a substitute for p1^.bal. As the value of p2 does
not change from the time it is assigned to b2 to the time it is referenced I
believe that you can safely remove the assignment to b2 as you have already
done.

Regards,
Chris

Chris Burrows
CFB Software
http://www.cfbsoftware.com

----
To unsubscribe, send a message with body "SIGNOFF BLACKBOX" to LISTSERV{([at]})nowhere.xy----boundary-LibPST-iamunique-1489252809_-_-
Content-type: application/rtf
Content-transfer-encoding: base64
Content-Disposition: attachment; filename="rtf-body.rtf"
e1xydGYxXGFuc2lcYW5zaWNwZzEyNTJcZnJvbXRleHQgXGRlZmYwe1xmb250dGJsDQp7XGYwXGZz
d2lzcyBBcmlhbDt9DQp7XGYxXGZtb2Rlcm4gQ291cmllciBOZXc7fQ0Ke1xmMlxmbmlsXGZjaGFy
c2V0MiBTeW1ib2w7fQ0Ke1xmM1xmbW9kZXJuXGZjaGFyc2V0MCBDb3VyaWVyIE5ldzt9fQ0Ke1xj
b2xvcnRibFxyZWQwXGdyZWVuMFxibHVlMDtccmVkMFxncmVlbjBcYmx1ZTI1NTt9DQpcdWMxXHBh
cmRccGxhaW5cZGVmdGFiMzYwIFxmMFxmczIwID4tLS0tLU9yaWdpbmFsIE1lc3NhZ2UtLS0tLVxw
YXINCj5Gcm9tOiBCbGFja0JveCBbbWFpbHRvOkJMQUNLQk9YQExJU1RTLk9CRVJPTi5DSF0gT24g
QmVoYWxmIE9mIFxwYXINCj5DYW1wYmVsbCwgUm9iZXJ0IChTRUxFWCBHQUxJTEVPLCBVSylccGFy
DQo+U2VudDogTW9uZGF5LCA1IFNlcHRlbWJlciAyMDExIDY6MzQgUE1ccGFyDQo+VG86IEJMQUNL
Qk9YQExJU1RTLk9CRVJPTi5DSFxwYXINCj5TdWJqZWN0OiBSZTogW0JMQUNLQk9YXSBBVkwgVHJl
ZXNccGFyDQo+XHBhcg0KPkJvYlxwYXINCj5ccGFyDQo+VGhhbmtzIGZvciB0aGUgcmVmZXJlbmNl
ICh3aHkgZGlkbid0IEkgbG9vayB0aGVyZSBmaXJzdD8pXHBhcg0KPlxwYXINCj5JbiBzZWN0aW9u
IDQuNS4yLCBpbiBwcm9jZWR1cmUgImJhbGFuY2VSIiwgdGhlcmUgaXMgYW4gXHBhcg0KPmFzc2ln
bm1lbnQgImIyIDo9IHAyLmJhbDsiLlxwYXINCj5ccGFyDQo+YjIgaXMgbmVpdGhlciBkZWNsYXJl
ZCBvciB1c2VkLCBhbmQgdGhpcyBhc3NpZ21lbnQgaXMgbm90IGluIFxwYXINCj50aGUgbWlycm9y
IHByb2NlZHVyZSAiYmFsYW5jZVIiLiBJIGd1ZXNzIHRoYXQgaXQgaXMgdGhlcmUgYnkgXHBhcg0K
PmVycm9yLCBhbmQgc2hvdWxkIHNpbXBseSBiZSBvbWl0dGVkLiBXaGVuIEkgZG8gdGhhdCB0aGUg
XHBhcg0KPnByb2NlZHVyZSBzZWVtcyB0byB3b3JrLlxwYXINCj5ccGFyDQo+SXMgdGhlcmUgYW5v
dGhlciB2ZXJzaW9uIG9mIHRoZSBib29rIChQYXNjYWwgb3IgTW9kdWxhLUlJKSBvbiBccGFyDQo+
dGhlIHdlYiBzbyBJIGNhbiBjaGVjayB3aGF0IHRoZXkgc2F5P1xwYXINCj5ccGFyDQpccGFyDQpS
b2JlcnQsXHBhcg0KXHBhcg0KSW4gdGhlIDE5ODIgTW9kdWxhLTIgZWRpdGlvbiBvZiB0aGUgYm9v
aywgYjIgd2FzIGEgbG9jYWwgdmFyaWFibGUgZGVjbGFyZWRccGFyDQphcyBhIHN1YnJhbmdlIHR5
cGU6XHBhcg0KXHBhcg0KICBiMSwgYjI6IC0xLi4rMTtccGFyDQpccGFyDQpUaGUgaW5pdGlhbCBh
c3NpZ25tZW50IHdhcyBlcXVpdmFsZW50OlxwYXINClxwYXINCiAgYjIgOj0gcDJeLmJhbDtccGFy
DQpccGFyDQphbmQgYjIgd2FzIHRoZW4gdXNlZCBpbiB0aGUgbGF0ZXIgc3RhdGVtZW50cy4gSW5z
dGVhZCBvZjpccGFyDQpccGFyDQogIElGIHAyLmJhbCA9IC0xIFRIRU4gcC5iYWwgOj0gMSBFTFNF
IHAuYmFsIDo9IDAgRU5EIDtccGFyDQogIElGIHAyLmJhbCA9ICsxIFRIRU4gcDEuYmFsIDo9IC0x
IEVMU0UgcDEuYmFsIDo9IDAgRU5EIDtccGFyDQpccGFyDQp0aGUgZXF1aXZhbGVudCBzdGF0ZW1l
bnRzIHdlcmU6XHBhcg0KXHBhcg0KICBJRiBiMiA9IC0xIFRIRU4gcC5iYWwgOj0gMSBFTFNFIHAu
YmFsIDo9IDAgRU5EIDtccGFyDQogIElGIGIyID0gKzEgVEhFTiBwMS5iYWwgOj0gLTEgRUxTRSBw
MS5iYWwgOj0gMCBFTkQgO1xwYXINClxwYXINCmIxIHdhcyB1c2VkIHNpbWlsYXJseSBhcyBhIHN1
YnN0aXR1dGUgZm9yIHAxXi5iYWwuIEFzIHRoZSB2YWx1ZSBvZiBwMiBkb2VzXHBhcg0Kbm90IGNo
YW5nZSBmcm9tIHRoZSB0aW1lIGl0IGlzIGFzc2lnbmVkIHRvIGIyIHRvIHRoZSB0aW1lIGl0IGlz
IHJlZmVyZW5jZWQgSVxwYXINCmJlbGlldmUgdGhhdCB5b3UgY2FuIHNhZmVseSByZW1vdmUgdGhl
IGFzc2lnbm1lbnQgdG8gYjIgYXMgeW91IGhhdmUgYWxyZWFkeVxwYXINCmRvbmUuXHBhcg0KXHBh
cg0KUmVnYXJkcyxccGFyDQpDaHJpc1xwYXINClxwYXINCkNocmlzIEJ1cnJvd3NccGFyDQpDRkIg
U29mdHdhcmVccGFyDQpodHRwOi8vd3d3LmNmYnNvZnR3YXJlLmNvbVxwYXINClxwYXINClxwYXIN
Ci0tLS1ccGFyDQpUbyB1bnN1YnNjcmliZSwgc2VuZCBhIG1lc3NhZ2Ugd2l0aCBib2R5ICJTSUdO
T0ZGIEJMQUNLQk9YIiB0byBMSVNUU0VSVkBMSVNUUy5PQkVST04uQ0hccGFyDQp9
----boundary-LibPST-iamunique-1489252809_-_---

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