Bonjour,
 
Je me pose la question de savoir quelle est la meilleure facon de stocker un arbre binaire.
Pour l'instant je stocke les fils gauches et droits de chaque noeud sous forme de pointeurs mais je me demandais si il n'existait pas de meilleure facon de faire (par exemple un tableau/vector de taille fixe alloué au depart avec les fils designés par indice).
 
L'arbre peut contenir plusieurs millions de noeuds mais est de taille fixe (je push mes noeuds dans un vector et quand j'ai fini je créé mon abre et je l'equilibre).
Le point critique au niveau temps doit etre le parcours de l'arbre.
 
La taille occupée en mémoire est aussi à prendre en compte.
 
 
Merci d'avance pour vos reponses.

Si tu as un tas, alors une structure tabulaire ça le fait.
Si ton arbre est grand : fais en sorte qu'il soit équilibré. Utilise un allocateur mémoire ne pas fragmenter ta mémoire comme un porc, tu y gagneras et en conso et mémoire et en temps de parcours.

 
l'arbre est en effet equilibré, mais n' pas une structure de tas. C'est en fait un kdtree, chaque noeud represente un plan de partitionnement  de l'espace, les noeuds de chaque sous arbre se situant de chaque coté de ce plan.
 
Donc tu me conseille plutot un vector avec la taille reservé au depart?

non je n'ai pas dit ça. je te conseille un vrai allocateur mémoire pour allouer chaque noeud efficacement (et pas avec un new). Si ton arbre est équilibré et figé, à ce moment là, tu peux envisager un stockage tabulaire.

 
ok merci, je vais donc commencer par garder la meme structure mais avec un allocateur et essayer ensuite en tabulaire et faire des tests de performance.

La requête étant un peu floue, je vais m'en tenir à des généralités.
 
Il est assez facile de tasser les noeuds - feuille ou interne - d'un tel kD-tree en 8 octets, et si on est attentif celà se fait sans pénalité d'accès.

L'usage de "déplacement" résoud plusieurs problèmes épineux (64bits etc...) et ce sans surcoût au parcours si on est sioux.
 
Généralement on a interêt à au moins allouer les noeuds par paire, c.a.d. que gauche & droite sont tjs contigus; celà amène des simplifications quand on traverse (notament pour le calcul d'adresse), une meilleur coherence etc...
 
Après, et selon les usages, il est possible de descendre à 4 octets, de placer les noeuds de façon à optimiser la cachabilité et autres finasseries. Les variations sont sans fins
 
Tjs est-il que sous cette forme on peut directement mmapper l'arbre ou le reloger (ce qui permet de "streamer" à la création + mmap derriere).
 
EDIT: j'ai oublié de préciser que celà supose un alignement idoine.

c'est certain, mais si ton bute est de mmaper pour un dump binaire directe, je pense qu'il est vraiment plus clair et plus simple de travailler avec une structure tabulaire plutot que de se reposer sur un allocateur mémoire pour ça. L'inconvénient c'est effectivement que si ton arbre n'est pas très équilibré, tu gaches beaucoup de mémoire. Cela dit, tu pourrais presque envisager d'utiliser des index plutot que des pointeurs, et à ce moment là, tu travailler dans un tableau de manière quasi-transparente. Tu maintiens une liste des noeuds libres pour pas scanner tout pour trouver une case de libre et voilà. Ça doit pouvoir fonctionner, à voir en termes de performances.

Je suppose qu'ArthurDent utilise son kD-tree pour du photon mapping, vu qu'il l'équilibre dans une dernière passe; je l'utilise plutôt pour du partitionnement spatial, les chances pour qu'il soit équilibré sont presques nulles.
Dans ce cas de figure l'arbre lui même ne represente qu'une part négligeable de la mémoire nécessaire à la phase de construction. De même il facile d'amortir qques passes en "post-process", si besoin est.
 
La question initiale étant l'optimisation du temps de parcours, il n'en reste pas moins que dans la forme que j'ai présenté, si node est le noeud courant alors (node + (node->offset & ~8)) ^ (8 & celui_de_droite) est le fils voulu; il me faut moins de 20 cycles/noeud pour faire traverser 4 rayons pour peu que je touche la cache.  
Difficile de faire mieux, donc.