Title :
On the Height of Multidimensional Height-Balanced Trees
Author :
Vaishnavi, Vljay K.
Author_Institution :
Department of Computer Information Systems, Georgia State University
Abstract :
It is shown that the worst case height of a k- dimensional height-balanced tree, k ≥ 2, is the same as that of an AVL-tree, to within an additive factor of 2k − 2.
Keywords :
Data structure analysis; dynamic databases; height-balanced trees; information storage and retrieval; multidimensional balanced tree structures; multidimensional height- balanced trees; Additives; Costs; Data analysis; Data structures; Databases; Information analysis; Information retrieval; Multidimensional systems; Tree data structures; Upper bound; Data structure analysis; dynamic databases; height-balanced trees; information storage and retrieval; multidimensional balanced tree structures; multidimensional height- balanced trees;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1986.1676837
