Re: [BLACKBOX] AVL Trees

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

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

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----boundary-LibPST-iamunique-1799204785_-_-
Content-type: application/rtf
Content-transfer-encoding: base64
Content-Disposition: attachment; filename="rtf-body.rtf"
e1xydGYxXGFuc2lcYW5zaWNwZzEyNTJcZnJvbXRleHQgXGRlZmYwe1xmb250dGJsDQp7XGYwXGZz
d2lzcyBBcmlhbDt9DQp7XGYxXGZtb2Rlcm4gQ291cmllciBOZXc7fQ0Ke1xmMlxmbmlsXGZjaGFy
c2V0MiBTeW1ib2w7fQ0Ke1xmM1xmbW9kZXJuXGZjaGFyc2V0MCBDb3VyaWVyIE5ldzt9fQ0Ke1xj
b2xvcnRibFxyZWQwXGdyZWVuMFxibHVlMDtccmVkMFxncmVlbjBcYmx1ZTI1NTt9DQpcdWMxXHBh
cmRccGxhaW5cZGVmdGFiMzYwIFxmMFxmczIwIFRoYW5rcyB0byBldmVyeW9uZSB3aG8gcHJvdmlk
ZWQgc3VnZ2VzdGlvbnMuXHBhcg0KXHBhcg0KXHBhcg0KSSBoYXZlIG5vdyBzb2x2ZWQgbXkgcHJv
YmxlbSAoNiBkaWZmZXJlbnQgd2F5cyEpIHNvIEkgZG9uJ3QgbmVlZCBhbnkgbW9yZSBzb2x1dGlv
bnMhXHBhcg0KXHBhcg0KXHBhcg0KVGhlIGlyb255IGlzIHRoYXQgSSBvcmlnaW5hbGx5IGFza2Vk
IGZvciBoZWxwIHdpdGggdGhlICdEZWxldGUnIHJvdXRpbmUuIEkgbm93XHBhcg0Ka25vdyB0aGF0
IEkgb25seSBuZWVkZWQgdG8gYnVpbGQgdGhlIGRhdGEgc3RydWN0dXJlIGFuZCB0cmF2ZXJzZSBp
dCBvbmNlOyBJIFxwYXINCmRpZG4ndCBhY3R1YWxseSBuZWVkIHRvIGRvIGFueSBkZWxldGluZy5c
cGFyDQpccGFyDQpccGFyDQpUaGUgcHJvYmxlbSB3YXMgY2hhcmFjdGVyaXNlZCBieSB0aHJlZSBp
bnRlZ2VyczogQyAoa25vd24gYW5kIGxhcmdlKSwgQiwgd2hpY2ggXHBhcg0KaXMgc21hbGxlciB0
aGFuIEMsIGFuZCBBICh0aGUgYW5zd2VyKSB3aGljaCBpcyBzbWFsbGVyIGFnYWluLlxwYXINClxw
YXINCkkgdGhvdWdodCB0aGF0IEEgd291bGQgYmUgKCptdWNoKikgc21hbGxlciB0aGFuIEIsIHdo
aWNoIHdvdWxkIGJlICgqbXVjaCopIFxwYXINCnNtYWxsZXIgdGhhbiBBLlxwYXINClxwYXINClxw
YXINClRoZXJlIHdlcmUgZm91ciBvYnZpb3VzIGFsZ29yaXRobXMgd2l0aCB0aGUgZm9sbG93aW5n
IHByb3BlcnRpZXM6XHBhcg0KXHBhcg0KRGF0YS1TdHJ1Y3R1cmVcdGFiIFJlcXVpcmVkLU1lbW9y
eVx0YWIgUmVxdWlyZWQtVGltZVxwYXINClxwYXINCkFycmF5XHRhYiBDXHRhYiBDXHBhcg0KTGlz
dFx0YWIgQVx0YWIgQiAqIEFccGFyDQpMaXN0XHRhYiBCXHRhYiBCICogTG9nIChCKVxwYXINClRy
ZWVcdGFiIEFcdGFiIEIgKiBMb2cgKEEpXHBhcg0KXHBhcg0KXHBhcg0KSSBydWxlZCBvdXQgdGhl
IEFycmF5IGFzIEkgdGhvdWdodCB0aGUgbWVtb3J5IHdvdWxkIGJlIHRvbyBiaWcuXHBhcg0KSW4g
ZmFjdCBpdCBpcyB0aGUgYmVzdC4gSXQgcmVxdWlyZXMgb25seSAxIGJpdCBwZXIgbm9kZSwgY29t
cGFyZWQgdG8gYVxwYXINCnRocmVhZGVkIEFWTCB0cmVlIHdoaWNoIHJlcXVpcmVzIGFib3V0IDEw
MCBiaXRzIHBlciBub2RlLCBzbyB0aGUgbWVtb3J5IHdhcyBccGFyDQphZmZvcmRhYmxlLlxwYXIN
ClxwYXINCkkgcnVsZWQgb3V0IHRoZSBMaXN0cyBhcyBJIHRob3VnaHQgdGhleSB3b3VsZCBiZSBl
aXRoZXIgdG9vIHNsb3cgKGNvcnJlY3QpIG9yIFxwYXINCnRvbyBiaWcuIEluIGZhY3QgQiBpcyBu
b3QgbXVjaCBiaWdnZXIgdGhhbiBBIHNvIHRoZSBsaXN0IHNvbHV0aW9uIGlzIGVmZmljaWVudCBc
cGFyDQphbmQgU0lNUExFIS5ccGFyDQpccGFyDQpUaGUgdGltZXMgYXJlOlxwYXINClxwYXINCkFy
cmF5XHRhYiBcdGFiIFx0YWIgXHRhYiAwLjIyIHNccGFyDQpTbG93IGxpc3RcdGFiIFx0YWIgXHRh
YiA+IDEwIGhvdXJzXHBhcg0KRmFzdCBsaXN0XHRhYiBcdGFiIFx0YWIgMS40MiBzXHBhcg0KVW5i
YWxhbmNlZCBiaW5hcnkgdHJlZVx0YWIgXHRhYiA4LjI4IHNccGFyDQpBVkwgdHJlZSAoTW9kdWxh
LTIgYm9vaylcdGFiIDEuMzkgc1xwYXINCkFWTCB0cmVlIChXaXJ0aCdzIGJvb2spXHRhYiBcdGFi
IDEuMyBzXHBhcg0KQVZMIHRyZWUgKFN1YnN5c3RlbSBVdGlsIG9uIENQQylcdGFiIDIuMCBzXHBh
cg0KXHBhcg0KXHBhcg0KVGhlIFV0aWwgdmVyc2lvbiBpcyBhIHRocmVhZGVkIHRyZWUsIHdoaWNo
IG1lYW5zIHRoYXQgaXQgaXMgYSBsaXR0bGUgbW9yZVxwYXINCmNvc3RseSB0byBidWlsZCwgYnV0
IG1vcmUgZWZmaWNpZW50IC8gZmxleGlibGUgdG8gYWNjZXNzOyBmZWF0dXJlcyBub3QgdXNlZCBo
ZXJlLlxwYXINClxwYXINClxwYXINCk5leHQgdGltZSAoaWYgdGhlcmUgaXMgYSBuZXh0IHRpbWUh
KSBJIHdpbGwgdXNlIGFuIHVuYmFsYW5jZWQgYmluYXJ5IHRyZWUuXHBhcg0KVGhlIGxpc3Qgd291
bGQgbm90IGhhdmUgYmVlbiBjb21wZXRpdGl2ZSBpZiBBIGhhZCBiZWVuICgqbXVjaCopIHNtYWxs
ZXIgdGhhbiBCLFxwYXINCmFuZCB0aGUgYWR2YW50YWdlIG9mIHRoZSBBVkwgdHJlZSBkb2VzIG5v
dCBqdXN0aWZ5IHRoZSBjb21wbGV4aXR5LlxwYXINClxwYXINClxwYXINClxwYXINCkNoZWVyc1xw
YXINClxwYXINClJvYmVydFxwYXINClxwYXINClxwYXINCi0tLS1ccGFyDQpUbyB1bnN1YnNjcmli
ZSwgc2VuZCBhIG1lc3NhZ2Ugd2l0aCBib2R5ICJTSUdOT0ZGIEJMQUNLQk9YIiB0byBMSVNUU0VS
VkBMSVNUUy5PQkVST04uQ0hccGFyDQp9
----boundary-LibPST-iamunique-1799204785_-_---

Received on Tue Sep 06 2011 - 23:20:13 UTC