| written by Donar on Jun 10, 2006 12:58 |
└> last changed by Donar on June 13, 2006 at 16:44
|
| written by Ponche on Jun 10, 2006 20:03 |
 | |  | | ![]() Are you planning to use this library for something in particular? | |  | |  |
|
| written by Donar on Jun 11, 2006 07:57 |
 | |  | |  | Ponche said: | | Are you planning to use this library for something in particular? |
Yes. However, I think your question is of a more general scope, as in "what are AVL trees good for?" To answer this, I maybe should first briefly explain what an AVL tree is. If you are familiar with those, simply skip the 2 next paragraphs.
In general, binary trees have the intention of reducing access time to a particular node identified by its key. However, normal binary trees usually lead to inefficient searches, especially when new nodes are fed in in already sorted order. Thus, balancing algorithms have been developed, with the goal to keep the "height" of the tree minimal (the distance between the root and the node to be found, i.e. the number of comparisons to find the node). A very efficient way to do so is the AVL tree, although its implementation is complex, particularly for deletions. AVL trees are efficient, because both worst-time /and/ average-time standard functions (insertion, node-access, removal) can be done in O(lg n) time.
However, other algorithms, for example "Red-Black trees" can perform in O(lg n) as well, thus examination of the maximum possible imbalance is helpful to compare different algorithms. For AVL trees, this number is higher than perfectly balanced trees (approx. 1.45*lg n), but it is better than for Red-Black trees (2*lg n). The fact, that Red-Black trees are used more often despite their weaker performance is due to the relatively high complexity of the implementation of AVL trees. Well, here you have a such, even in a high-speed language 
Now for my intended usage: I need to access a high number of records (in the quantity of several millions), all identified by a particular key. There is an initial tree building routine providing most of those nodes. During process, more new nodes are added, and others deleted. What I need, though, is a very fast access to the existing nodes, identified by their keys. These accesses come at a huge volume, thus perfectly balanced trees would be the choice for it. However, keeping those perfectly balanced comes at a too high expense, as there are additional insertions and deletions for which a perfect balance is extreme overhead. For such purposes (relatively stable but not static tree with lots of accesses), AVL trees are the most suitable choice.
For what can /you/ use them? Well, that's up to you, of course. The following proposal is not to be taken for serious, but it may give you the idea: Read in your local telephone directory sorted by phone number and later on access the record associated with it, while constantly updating new subscribers and removing ceased ones.
Hope this answers your question. Some more infos can be found at the links below.
Regards
//Herbert
http://herbert.wikispaces.com/AVL+Tree
http://en.wikipedia.org/wiki/AVL_tree (but the German equivalent has much more details)
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/ | |  | |  |
|
  | written by Ponche on Jun 11, 2006 10:55 |
| | | | ![]() Well, thanks for the explanation but they told me that 2 o 3 years ago in class, so my question really was if you have implemented this library because you need it for some project in particular, or just for love-to-art. | | | | |
|
| written by Donar on Jun 11, 2006 19:45 |
| | | | | Ponche said: | | so my question really was if you have implemented this library because you need it for some project in particular, or just for love-to-art. |
For both. The former never should be done without the latter, or one has the wrong profession
Regards
//Herbert | | | | |
|
| | | | ![]() The library is looking good. : )
I should note that around line 1182 of the source, you seem to have inserted an extra ; character in a code label, causing it to bring up an error with the 1.2 compiler. The line appears as ";Avl Rebalance Right". Other than that, I didn't notice any obvious errors, although I didn't test it much yet, either. | | | | |
|
| written by Donar on Jun 12, 2006 05:06 |
| | | | | Cryoburner said: | | The library is looking good. : ) |
Thank you : )
| Cryoburner said: | | I should note that around line 1182 of the source, you seem to have inserted an extra ; character in a code label, causing it to bring up an error with the 1.2 compiler. The line appears as ";Avl Rebalance Right". Other than that, I didn't notice any obvious errors, although I didn't test it much yet, either. |
I can't see any superfluous semicolon in the source. Also Lino 1.13.11b does not complain. The surroundings look like this:
-> Avl Rebalance LL;
(-------------------------------------------------------------------------)
(A is rightheavy, examine right child's balance.)
"Avl Rebalance Right"
C = [A plus AVL RIGHT];
Maybe a flaw within the new compiler?
Regards
//Herbert | | | | |
|
└> last changed by Donar on June 12, 2006 at 05:21
|
| | | | ![]() Hmm, it looks more like a flaw in Opera9 beta2 when rendering that particular page. For some reason, it throws a spare semicolon in there. : )
It only appears in that one place though, and all the other quote marks appear correctly on that same page. Interestingly enough, if I resave the page's source with Opera9's internal html viewer, that line is displayed as it should be.
I suppose it might be better (and more convenient) if you also provided copies of your libraries as zipped text files. : ) | | | | |
|
| written by Donar on Jun 12, 2006 06:30 |
| | | | | Cryoburner said: | | I suppose it might be better (and more convenient) if you also provided copies of your libraries as zipped text files. : ) |
Took your advice, thank you. Uploaded [1].
Regards
//Herbert
[1] http://herbert.wikispaces.com/AVL+Tree | | | | |
|
└> last changed by Donar on June 13, 2006 at 09:08
|
|
