An implementation of a multidimensional dynamic range tree based on an AVL tree
| dc.contributor.author | Lamoureux, Michael, G. | |
| dc.date.accessioned | 2023-03-01T18:29:43Z | |
| dc.date.available | 2023-03-01T18:29:43Z | |
| dc.date.issued | 1995 | |
| dc.description.abstract | 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 | |
| dc.description.copyright | Copyright @ Michael G. Lamoureux, 1995. | |
| dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/14944 | |
| dc.rights | http://purl.org/coar/access_right/c_abf2 | |
| dc.subject.discipline | Computer Science | |
| dc.title | An implementation of a multidimensional dynamic range tree based on an AVL tree | |
| dc.type | technical report |
Files
Original bundle
1 - 1 of 1