Multidimensional balanced binary trees
Vijay K. Vaishnavi · IEEE Transactions on Computers · 1989
A new balanced multidimensional tree structure called a k-dimensional balanced binary tree, where k is a positive integer, is presented and integrated. It is shown that the data structure can be used to manage a set of n k-dimensional data items such that access, insertion, and deletion operations can be supported in O(log n+k) time. The data structure is a multidimensional generalization of a balanced binary tree and retains much of the simplicity and efficiency of the base structure. The data structure requires O(k) single rotations for each insertion or deletion operation.>