Je cherche des façons de concevoir au mieux un arbre N-aire qui utilisera efficacement le cache. Je m'attends à ce que la grande majorité des opérations sur l'arbre soit traversée par un nœud à la racine, donc c'est l'utilisation que je veux cibler, je pense que les insertions/suppressions sont assez coûteuses.Conception d'un arbre N-aire optimisé en cache
Sur ma tête, stocker les nœuds d'avant en arrière (c'est-à-dire la racine à la fin) est une propriété désirée. Et puis je suppose que vous pouvez le stocker soit dans BFS ou DFS - ce qui est le mieux pour ce cas? Est-ce important, une fois que l'arbre atteint une certaine taille?
J'ai également brièvement rencontré ce http://www.cs.au.dk/~gerth/papers/soda02.pdf - cela semble prometteur mais ce n'est pas un BST et je n'ai pas besoin de chercher d'aucune sorte, juste traversée de l'enfant à la racine.
EDIT: Oui, il faudra l'implémenter en plus de vector/array, donc de la mémoire contiguë. Il n'a pas besoin d'être un BST. Les nœuds sont accédés directement via la propriété d'accès aléatoire des vecteurs/tableaux, c'est la traversée à la racine à partir de là qui est la question
Des idées?
_Why_ tu parcours de l'arbre? Pour trouver les nœuds entre les feuilles et la racine, je suppose? Comment trouvez-vous le bon noeud feuille en premier lieu? Si vous trouvez des feuilles via un 'Noeud *', vous ne pouvez pas les déplacer, ce qui complique les insertions. – MSalters
Pourriez-vous stocker vos nœuds dans une structure de données contiguë, telle qu'un vecteur? Quelle est la taille de vos données et quelle est la taille de votre arbre? –
Je ne suis pas sûr d'avoir parfaitement compris la question, mais si vous voulez un BST qui utilise le cache, choisissez un arbre B +. Il y a déjà un tas d'implémentations qui traînent. https://en.wikipedia.org/wiki/B%2B_tree – AlexG