A method traverses a bi-tree stored in a memory to locate application
specific data stored in the memory and associated with the bi-tree. The
bi-tree comprises a spatial partitioning of an N-dimensional space into a
hierarchy of cells. Starting from a root cell enclosing the N-dimensional
space, each cell is successively and conditionally partitioned into
2.sup.N child cells along the cell's N mid-planes. Each cell of the
bi-tree has associated characteristics comprising the application specific
data and child cells are indexed directly from a parent cell. First, a set
of locational codes, a cell of the bi-tree, and a termination condition
are specified. Next, the characteristics of the cell are tested to see if
they satisfy the termination condition. If the termination condition is
not satisfied, an arithmetic operation on the set of locational codes is
performed to directly index a next cell to be tested. Otherwise, the cell
identifies a target cell. Finally, the application specific data of the
target cell is retrieved from the memory.
Une méthode traverse un Bi-arbre stocké dans une mémoire pour localiser des données spécifiques d'application stockées dans la mémoire et liées à l'Bi-arbre. L'Bi-arbre comporte une division spatiale d'un espace dimensionnel de N dans une hiérarchie des cellules. À partir d'une cellule de racine enfermant l'espace dimensionnel de N, chaque cellule successivement et conditionnellement est divisée dans des cellules de l'enfant 2.sup.N le long des mi-avions du N des cellules. Chaque cellule de l'Bi-arbre a associé des caractéristiques comportant les données spécifiques d'application et des cellules d'enfant sont classées directement d'une cellule de parent. D'abord, un ensemble de codes localisés, une cellule de l'Bi-arbre, et un état d'arrêt sont indiqués. Après, les caractéristiques de la cellule sont examinées pour voir si elles satisfont la condition d'arrêt. Si la condition d'arrêt n'est pas satisfaite, une opération arithmétique sur l'ensemble de codes localisés est effectuée pour classer directement une prochaine cellule à examiner. Autrement, la cellule identifie une cellule de cible. En conclusion, les données spécifiques d'application de la cellule de cible sont recherchées de la mémoire.
