Re: [BLACKBOX] AVL Trees

From: [at]} <Gérard>
Date: Wed, 7 Sep 2011 03:00:09 +0200

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

Hello Robert,

What do you call a fast list?

Gérard

Le mardi 06 septembre 2011 à 22:20 +0100, Robert a écrit :
> Thanks to everyone who provided suggestions.
>
>
> I have now solved my problem (6 different ways!) so I don't need any more solutions!
>
>
> The irony is that I originally asked for help with the 'Delete' routine. I now
> know that I only needed to build the data structure and traverse it once; I
> didn't actually need to do any deleting.
>
>
> The problem was characterised by three integers: C (known and large), B, which
> is smaller than C, and A (the answer) which is smaller again.
>
> I thought that A would be (*much*) smaller than B, which would be (*much*)
> smaller than A.
>
>
> There were four obvious algorithms with the following properties:
>
> Data-Structure Required-Memory Required-Time
>
> Array C C
> List A B * A
> List B B * Log (B)
> Tree A B * Log (A)
>
>
> I ruled out the Array as I thought the memory would be too big.
> In fact it is the best. It requires only 1 bit per node, compared to a
> threaded AVL tree which requires about 100 bits per node, so the memory was
> affordable.
>
> I ruled out the Lists as I thought they would be either too slow (correct) or
> too big. In fact B is not much bigger than A so the list solution is efficient
> and SIMPLE!.
>
> The times are:
>
> Array 0.22 s
> Slow list > 10 hours
> Fast list 1.42 s
> Unbalanced binary tree 8.28 s
> AVL tree (Modula-2 book) 1.39 s
> AVL tree (Wirth's book) 1.3 s
> AVL tree (Subsystem Util on CPC) 2.0 s
>
>
> The Util version is a threaded tree, which means that it is a little more
> costly to build, but more efficient / flexible to access; features not used here.
>
>
> Next time (if there is a next time!) I will use an unbalanced binary tree.
> The list would not have been competitive if A had been (*much*) smaller than B,
> and the advantage of the AVL tree does not justify the complexity.
>
>
>
> 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----boundary-LibPST-iamunique-1257188583_-_-
Content-type: application/rtf
Content-transfer-encoding: base64
Content-Disposition: attachment; filename="rtf-body.rtf"
e1xydGYxXGFuc2lcYW5zaWNwZzEyNTJcZnJvbXRleHQgXGRlZmYwe1xmb250dGJsDQp7XGYwXGZz
d2lzc1xmY2hhcnNldDAgQXJpYWw7fQ0Ke1xmMVxmbW9kZXJuIENvdXJpZXIgTmV3O30NCntcZjJc
Zm5pbFxmY2hhcnNldDIgU3ltYm9sO30NCntcZjNcZm1vZGVyblxmY2hhcnNldDAgQ291cmllciBO
ZXc7fX0NCntcY29sb3J0YmxccmVkMFxncmVlbjBcYmx1ZTA7XHJlZDBcZ3JlZW4wXGJsdWUyNTU7
fQ0KXHVjMVxwYXJkXHBsYWluXGRlZnRhYjM2MCBcZjBcZnMyMCBIZWxsbyBSb2JlcnQsXHBhcg0K
XHBhcg0KV2hhdCBkbyB5b3UgY2FsbCBhIGZhc3QgbGlzdD9ccGFyDQpccGFyDQpHXCdlOXJhcmRc
cGFyDQpccGFyDQpMZSBtYXJkaSAwNiBzZXB0ZW1icmUgMjAxMSBcJ2UwIDIyOjIwICswMTAwLCBS
b2JlcnQgYSBcJ2U5Y3JpdCA6XHBhcg0KPiBUaGFua3MgdG8gZXZlcnlvbmUgd2hvIHByb3ZpZGVk
IHN1Z2dlc3Rpb25zLlxwYXINCj4gXHBhcg0KPiBccGFyDQo+IEkgaGF2ZSBub3cgc29sdmVkIG15
IHByb2JsZW0gKDYgZGlmZmVyZW50IHdheXMhKSBzbyBJIGRvbid0IG5lZWQgYW55IG1vcmUgc29s
dXRpb25zIVxwYXINCj4gXHBhcg0KPiBccGFyDQo+IFRoZSBpcm9ueSBpcyB0aGF0IEkgb3JpZ2lu
YWxseSBhc2tlZCBmb3IgaGVscCB3aXRoIHRoZSAnRGVsZXRlJyByb3V0aW5lLiBJIG5vd1xwYXIN
Cj4ga25vdyB0aGF0IEkgb25seSBuZWVkZWQgdG8gYnVpbGQgdGhlIGRhdGEgc3RydWN0dXJlIGFu
ZCB0cmF2ZXJzZSBpdCBvbmNlOyBJIFxwYXINCj4gZGlkbid0IGFjdHVhbGx5IG5lZWQgdG8gZG8g
YW55IGRlbGV0aW5nLlxwYXINCj4gXHBhcg0KPiBccGFyDQo+IFRoZSBwcm9ibGVtIHdhcyBjaGFy
YWN0ZXJpc2VkIGJ5IHRocmVlIGludGVnZXJzOiBDIChrbm93biBhbmQgbGFyZ2UpLCBCLCB3aGlj
aCBccGFyDQo+IGlzIHNtYWxsZXIgdGhhbiBDLCBhbmQgQSAodGhlIGFuc3dlcikgd2hpY2ggaXMg
c21hbGxlciBhZ2Fpbi5ccGFyDQo+IFxwYXINCj4gSSB0aG91Z2h0IHRoYXQgQSB3b3VsZCBiZSAo
Km11Y2gqKSBzbWFsbGVyIHRoYW4gQiwgd2hpY2ggd291bGQgYmUgKCptdWNoKikgXHBhcg0KPiBz
bWFsbGVyIHRoYW4gQS5ccGFyDQo+IFxwYXINCj4gXHBhcg0KPiBUaGVyZSB3ZXJlIGZvdXIgb2J2
aW91cyBhbGdvcml0aG1zIHdpdGggdGhlIGZvbGxvd2luZyBwcm9wZXJ0aWVzOlxwYXINCj4gXHBh
cg0KPiBEYXRhLVN0cnVjdHVyZVx0YWIgUmVxdWlyZWQtTWVtb3J5XHRhYiBSZXF1aXJlZC1UaW1l
XHBhcg0KPiBccGFyDQo+IEFycmF5XHRhYiBDXHRhYiBDXHBhcg0KPiBMaXN0XHRhYiBBXHRhYiBC
ICogQVxwYXINCj4gTGlzdFx0YWIgQlx0YWIgQiAqIExvZyAoQilccGFyDQo+IFRyZWVcdGFiIEFc
dGFiIEIgKiBMb2cgKEEpXHBhcg0KPiBccGFyDQo+IFxwYXINCj4gSSBydWxlZCBvdXQgdGhlIEFy
cmF5IGFzIEkgdGhvdWdodCB0aGUgbWVtb3J5IHdvdWxkIGJlIHRvbyBiaWcuXHBhcg0KPiBJbiBm
YWN0IGl0IGlzIHRoZSBiZXN0LiBJdCByZXF1aXJlcyBvbmx5IDEgYml0IHBlciBub2RlLCBjb21w
YXJlZCB0byBhXHBhcg0KPiB0aHJlYWRlZCBBVkwgdHJlZSB3aGljaCByZXF1aXJlcyBhYm91dCAx
MDAgYml0cyBwZXIgbm9kZSwgc28gdGhlIG1lbW9yeSB3YXMgXHBhcg0KPiBhZmZvcmRhYmxlLlxw
YXINCj4gXHBhcg0KPiBJIHJ1bGVkIG91dCB0aGUgTGlzdHMgYXMgSSB0aG91Z2h0IHRoZXkgd291
bGQgYmUgZWl0aGVyIHRvbyBzbG93IChjb3JyZWN0KSBvciBccGFyDQo+IHRvbyBiaWcuIEluIGZh
Y3QgQiBpcyBub3QgbXVjaCBiaWdnZXIgdGhhbiBBIHNvIHRoZSBsaXN0IHNvbHV0aW9uIGlzIGVm
ZmljaWVudCBccGFyDQo+IGFuZCBTSU1QTEUhLlxwYXINCj4gXHBhcg0KPiBUaGUgdGltZXMgYXJl
OlxwYXINCj4gXHBhcg0KPiBBcnJheVx0YWIgXHRhYiBcdGFiIFx0YWIgMC4yMiBzXHBhcg0KPiBT
bG93IGxpc3RcdGFiIFx0YWIgXHRhYiA+IDEwIGhvdXJzXHBhcg0KPiBGYXN0IGxpc3RcdGFiIFx0
YWIgXHRhYiAxLjQyIHNccGFyDQo+IFVuYmFsYW5jZWQgYmluYXJ5IHRyZWVcdGFiIFx0YWIgOC4y
OCBzXHBhcg0KPiBBVkwgdHJlZSAoTW9kdWxhLTIgYm9vaylcdGFiIDEuMzkgc1xwYXINCj4gQVZM
IHRyZWUgKFdpcnRoJ3MgYm9vaylcdGFiIFx0YWIgMS4zIHNccGFyDQo+IEFWTCB0cmVlIChTdWJz
eXN0ZW0gVXRpbCBvbiBDUEMpXHRhYiAyLjAgc1xwYXINCj4gXHBhcg0KPiBccGFyDQo+IFRoZSBV
dGlsIHZlcnNpb24gaXMgYSB0aHJlYWRlZCB0cmVlLCB3aGljaCBtZWFucyB0aGF0IGl0IGlzIGEg
bGl0dGxlIG1vcmVccGFyDQo+IGNvc3RseSB0byBidWlsZCwgYnV0IG1vcmUgZWZmaWNpZW50IC8g
ZmxleGlibGUgdG8gYWNjZXNzOyBmZWF0dXJlcyBub3QgdXNlZCBoZXJlLlxwYXINCj4gXHBhcg0K
PiBccGFyDQo+IE5leHQgdGltZSAoaWYgdGhlcmUgaXMgYSBuZXh0IHRpbWUhKSBJIHdpbGwgdXNl
IGFuIHVuYmFsYW5jZWQgYmluYXJ5IHRyZWUuXHBhcg0KPiBUaGUgbGlzdCB3b3VsZCBub3QgaGF2
ZSBiZWVuIGNvbXBldGl0aXZlIGlmIEEgaGFkIGJlZW4gKCptdWNoKikgc21hbGxlciB0aGFuIEIs
XHBhcg0KPiBhbmQgdGhlIGFkdmFudGFnZSBvZiB0aGUgQVZMIHRyZWUgZG9lcyBub3QganVzdGlm
eSB0aGUgY29tcGxleGl0eS5ccGFyDQo+IFxwYXINCj4gXHBhcg0KPiBccGFyDQo+IENoZWVyc1xw
YXINCj4gXHBhcg0KPiBSb2JlcnRccGFyDQo+IFxwYXINCj4gXHBhcg0KPiAtLS0tXHBhcg0KPiBU
byB1bnN1YnNjcmliZSwgc2VuZCBhIG1lc3NhZ2Ugd2l0aCBib2R5ICJTSUdOT0ZGIEJMQUNLQk9Y
IiB0byBMSVNUU0VSVkBMSVNUUy5PQkVST04uQ0hccGFyDQo+IFxwYXINClxwYXINClxwYXINCi0t
LS1ccGFyDQpUbyB1bnN1YnNjcmliZSwgc2VuZCBhIG1lc3NhZ2Ugd2l0aCBib2R5ICJTSUdOT0ZG
IEJMQUNLQk9YIiB0byBMSVNUU0VSVkBMSVNUUy5PQkVST04uQ0hccGFyDQp9
----boundary-LibPST-iamunique-1257188583_-_---

Received on Wed Sep 07 2011 - 03:00:09 UTC