TY - JOUR

T1 - Generalized k-d-trees and local reorganizations

AU - Lebedinskaya, N. A.

AU - Lebedinskii, D. M.

N1 - Funding Information: ACKNOWLEDGMENTS This work was financially supported in part by the Russian Foundation for Basic Research, project nos. 10 01 00 245 and 10 01 00 297.

PY - 2012/7

Y1 - 2012/7

N2 - This work is devoted to the problem of organization of data structure for the realization of a multidimensional dictionary. In this paper, a generalization of k-d-trees is suggested, which admits local reorganizations in contrast to the classical version. Also, in addition to the multidimensional analog of rotations, a new type of local reorganizations is introduced. Unfortunately, in contrast to the classical one-dimensional case, reorganizations of this kind are not always applicable to a particular node; this work suggests necessary and sufficient conditions for all kinds of local reorganizations under study to be applicable to a particular node of the tree. By elementary means we prove a theorem that generalizes a well known result on binary search trees, namely, any tree of this kind may be transformed into any other tree with the same set of keys by a sequence of local reorganizations each involving only one node and its children. This kind of trees may be employed in the organization of storage of multi-dimensional data. Here, perfect analogy with the one-dimensional case is hardly feasible, because the application of the reorganizations described above to a particular node requires special processing of both of its children. However, in systems which involve a separate process for tree structure optimization concurrently with the use of the tree, the feasibility of performing an arbitrary reorganization of the tree structure with the use of a sequence of only local reorganizations seems to be a significant advantage.

AB - This work is devoted to the problem of organization of data structure for the realization of a multidimensional dictionary. In this paper, a generalization of k-d-trees is suggested, which admits local reorganizations in contrast to the classical version. Also, in addition to the multidimensional analog of rotations, a new type of local reorganizations is introduced. Unfortunately, in contrast to the classical one-dimensional case, reorganizations of this kind are not always applicable to a particular node; this work suggests necessary and sufficient conditions for all kinds of local reorganizations under study to be applicable to a particular node of the tree. By elementary means we prove a theorem that generalizes a well known result on binary search trees, namely, any tree of this kind may be transformed into any other tree with the same set of keys by a sequence of local reorganizations each involving only one node and its children. This kind of trees may be employed in the organization of storage of multi-dimensional data. Here, perfect analogy with the one-dimensional case is hardly feasible, because the application of the reorganizations described above to a particular node requires special processing of both of its children. However, in systems which involve a separate process for tree structure optimization concurrently with the use of the tree, the feasibility of performing an arbitrary reorganization of the tree structure with the use of a sequence of only local reorganizations seems to be a significant advantage.

KW - k-d-trees

KW - local reorganizations

KW - multidimensional data

UR - http://www.scopus.com/inward/record.url?scp=84866159291&partnerID=8YFLogxK

U2 - 10.3103/S1063454112030028

DO - 10.3103/S1063454112030028

M3 - Article

AN - SCOPUS:84866159291

VL - 45

SP - 125

EP - 127

JO - Vestnik St. Petersburg University: Mathematics

JF - Vestnik St. Petersburg University: Mathematics

SN - 1063-4541

IS - 3

ER -