SYMMETRICAL (AND GENERIC) ALGORITHMS FOR HEIGHT BALANCED TREES

Most algorithms for height balanced trees (or AVL-trees, after Adelson-Velskii and Landis [1]) suffer from a lack of exploitation of the symmetry of balance restoring operations when insertions and deletions in such tree structures are being made. Either we find algorithms in duplicate (i.e., written separately for left and right subtrees [6,7] or only the principle is described, stating that the other case follows from the first by a straightforward substitution [4].

We present an algorithm in which this symmetry is fully exploited and therefore the left and right algorithms can be mapped onto each other. Furthermore, the interface with the application is fully generic, i.e., the algorithm is fit for application in any environment, regardless of the kind of data being stored in the tree.

Besides, we use a textual representation for binary trees that is both more general and more amenable to analysis than the customary pictorial representation (which - at best - serves an exemplary purpose).