AVL Tree
|
URI: |
http://herbert.gandraxa.com/herbert/avl.asp |
|
Link template: |
<a href="http://herbert.gandraxa.com/herbert/avl.asp">AVL Tree</a> |
|
Link symbols: |
|
On current page |
ZIP archive |
PDF |
E-Mail
Article
Organization
Home »
Linoleum Source Code » AVL Tree
- Source Code Library: The implementation in the cross-platform Assembler Linoleum.
- Source Code Test Program: Test program using the library.
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
External Pages
- AVL Tree on Wikipedia, by far more detailled on the German Wikipedia though
The Data Structure: Brief explanation of the data structure [NIST]
Download
The following ZIP file contains both the library's source (AVL.txt) as well as a test program (AVL Test.txt).
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 an 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.
