Multidimensional Height-Balanced Trees
Author:
- 1 April 1984
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-33 (4) , 334-343
Abstract
A new multidimensional balanced tree structure is presented for the efficient management of multidimensional data. It is shown that the data structure can be used to manage a set of n k-dimensional records or data items such that the records can be searched or updated in O(log2 n) + k time, which is optimal. The data structure is a multidimensional generalization of the height-balanced trees and retains much of their simplicity and efficiency. The insertion algorithm, in particular, retains a very important property of the height-balanced trees: an insertion of a record results in the application of a restructuring operation at most once.Keywords
This publication has 27 references indexed in Scilit:
- Rectilinear line segment intersection, layered segment trees, and dynamizationJournal of Algorithms, 1982
- Computing Point EnclosuresIEEE Transactions on Computers, 1982
- Weighted multidimensional B-trees used as nearly optimal dynamic dictionariesLecture Notes in Computer Science, 1981
- Data structures for the rectangle containment and enclosure problemsComputer Graphics and Image Processing, 1980
- Performance evaluation of attribute-based tree organizationACM Transactions on Database Systems, 1980
- Multidimensional B-tree: An efficient dynamic file structure for exact match queries1980
- Height balanced 2–3 treesComputing, 1979
- A dichromatic framework for balanced trees1978
- Analysis of the Multiple-Attribute-Tree Data-Base OrganizationIEEE Transactions on Software Engineering, 1977
- Quad trees a data structure for retrieval on composite keysActa Informatica, 1974