AVL Tree
This document was visited 10 times in the recent 24 hours, and 140 times in the recent 7 days.
|
|
Link symbols:
|
 On current page |
 On this site |
 On external site |
 Wikipedia article |
 ZIP archive |
 PDF |
 E-Mail
If a flag appears after such a symbol, then it indicates, that the linked page is not in English language, but in the language spoken natively in the country represented by that flag.
|
Discussion: |
Find Gandraxa in Facebook |
|
|
Links:
|
Links are what make the Web work. Consequenly, you are most welcome to link any of my pages without asking for permission. If you plan to do so for this page, the following might be useful.
|
|
URI:
|
http://herbert.gandraxa.com/herbert/avl.asp
|
|
HTML template:
|
<a href="http://herbert.gandraxa.com/herbert/avl.asp">AVL Tree</a>
|
Article
Organization
Home »
Linoleum Source Code » AVL Tree
Download as a WinZip file see below.
Scope
Full-featured height-balanced binary AVL trees, implementation in the Linoleum Programming Language.
The AVL Tree Library implements an AVL Tree as published 1962 in the paper "An algorithm for the organization of information" by its inventors Georgy Maximovich Adelson-Velsky and Yevgeniy Mikhailovich Landis.
AVL trees have the characteristics to allow Lookups, Insertions and Deletions in O(log n) time both in worst and average case, making them ideal for the maintancance of a large quantity of information items.
This implementation additionally focusses on keeping the AVL tree as compact as possible in a dedicated storage area, producing zero fragmentation. In that storage area, the tree grows from top to bottom down to a given lower storage limit. The currently unused space between the actual lower extent and the physical lower storage limit can be used by the library user to store a node's payload, to which the node's data field points to. If this is done, then the lower storage boundary must be updated in order to avoid the current low end of the tree to interfer with user data, or vice-versa.
Author
Herbert Glarner
External Pages
Download
The following ZIP file contains both the library's source (AVL.txt) as well as a test program (AVL Test.txt).
AVL.zip
Test
The implementation was thoroughly tested for every operation and passed mass-data tests for 20 million nodes: it should run error-free.
Speed
PRNs = Pseudo Random Numbers
On a single-CPU Intel Celeron D 346 with 3,066 MHz, running Windows 2000 Professional, the current version 1.3 provided the following times for large-volume data:
| Number of Random Nodes [1] |
1 million |
5 million |
10 million |
20 million |
| Add Nodes |
2.4 sec |
17.1 sec |
39.3 sec |
89.5 sec |
| Find Nodes (by Key) |
2.3 sec |
16.4 sec |
36.9 sec |
84.1 sec |
| Remove Nodes |
2.9 sec |
19.7 sec |
48.6 sec |
119.0 sec |
[1] Random 31 bit keys; generated with the Mersenne Twister.
Found what you were looking for? Consider a donation.
