An implementation of a multidimensional dynamic range tree based on an AVL tree

Description

In this paper we develop a dynamic multidimensional range tree data structure based on the AVL tree. The range tree was originally defined as a static data structure which is optimal (O(lg[superscript k]n + t) for t points in range), in a worst case analysis, for answering k-dimensional range queries on k-dimensional data when only O(nlg[superscript k-1]n) space is used. Theoretical modifications to the structure do exist such that the structure can be used in a dynamic environment and maintain both its low range search time and storage requirements (in fact, the structure is optimally balanced), but, to the extent of the author's knowledge, a detailed specification of the structure along with a corresponding implementation does not yet exist in the literature. This paper defines the necessary transformations that are needed to transform the AVL tree into a 1-d dynamic range tree and the necessary modifications that are needed to extend this structure into a k-dimensional structure that can handle k-dimensional data. The resulting structure satisfies the specifications for a dynamic range tree and is optimally balanced. It is implemented in Pascal with complete code being provided in the appendices. This structure is important as it provides us with a baseline structure against which other structures, and their implementations, designed to handle multidimensional range queries on multidimensional data can be compared. Keywords: range tree, AVL tree, range query, multidimensional data, dynamic data structures, optimally balanced data structures