A data structure and related data storage and retrieval method rapidly
provide a count of elements stored or referenced by a hierarchical
structure of ordered elements (e.g., a tree), access to elements based on
their ordinal value in the structure, and identification of the ordinality
of elements. In an ordered tree implementation of the invention, a count
of elements stored in each subtree is stored, i.e., the cardinality of
each subtree is stored either at or associated with a higher level node
pointing to that subtree or at or associated with the head node of the
subtree. In addition to data structure specific requirements (e.g.,
creation of a new node, reassignment of pointers, balancing, etc.) data
insertion and deletion includes steps of updating affected counts.
Elements may be target data itself (e.g., data samples, prime numbers);
keys or indices associated with target data (e.g., social security numbers
of employees, product numbers and codes, etc. uses to reference associated
data records, etc.); or internal memory pointer to keys or data stored
external to the data structure. The invention is applicable to varied
hierarchical storage structures including, for example, binary trees, AVL
trees (height-balanced binary trees), b-trees, etc. (population based
structures) and digital trees (i.e., tries--expanse based structures).
Une structure de données et une méthode relative de stockage et de récupération de données fournissent rapidement un compte d'éléments stockés ou référencés par une structure hiérarchique des éléments commandés (par exemple, un arbre), l'accès aux éléments basés sur leur valeur ordinale dans la structure, et l'identification de l'ordinality des éléments. Dans une exécution commandée d'arbre de l'invention, un compte d'éléments stockés dans chaque sous-arbre est stocké, c.-à-d., la cardinalité de chaque sous-arbre est stockée à ou associée à un noeud de niveau plus élevé se dirigeant à ce sous-arbre ou à ou associée au noeud principal du sous-arbre. En plus des conditions spécifiques de structure de données (par exemple, création d'un nouveau noeud, rattribution des indicateurs, équilibrage, etc...) l'insertion et la suppression de données inclut des étapes de mettre à jour des comptes affectés. Les éléments peuvent être les données de cible elle-même (par exemple, des échantillons de données, des nombres principaux) ; les clefs ou les index se sont associés aux données de cible (par exemple, les nombres de sécurité sociale d'employés, nombres et codes de produit, etc. emploie pour mettre en référence les enregistrements, etc.. associés.) ; ou l'indicateur de mémoire interne aux clefs ou aux données a stocké externe à la structure de données. L'invention est applicable aux structures hiérarchiques diverses de stockage comprenant, par exemple, les arbres binaires, les arbres d'AVL (arbres binaires taille-équilibrés), les arbres binaires, etc. (structures basées par population) et les arbres numériques (c.-à-d., essais -- les structures basées par étendue).
