Discussion :

[SteelBox]

Bonjour
Savez vous comment on peut implémenter le plus efficacement possible un arbre binaire avec la STL ?
Merci

[Laurent Gomila]

Tu as ici un exemple d'arbre STL-like.

http://www.codeproject.com/Purgatory/Simple_STL_tree.asp

Je ne me rappelle plus du contenu, mais vu le site ça ne devrait pas être moche.

[SteelBox]

En fait, son exemple, c'est pour les arbres en général. Dans le cas d'un arbre binaire (un noeud a 2 fils), je ne crois pas qu'il soit très optimisé d'utiliser un vecteur...
Sinon, c'est effectivement une bonne idée
Merci

[Laurent Gomila]

Ben... oui, dans un arbre binaire tu auras juste un champ FilsDroit et un champ FilsGauche . En fait l'implémentation en elle-même n'est pas difficile, pour un arbre binaire "simple". L'important est de bien optimiser ses algos récursifs pour ne pas augmenter inutiulement la complexité de telle ou telle fonction. Après, vouloir le coder "avec la STL" n'est pas en soi une fin, l'interet pourrait par contre être de lui donner une interface STL-friendly, par exemple.

[SteelBox]

une interface STL-friendly

C'est quoi exactement ?
Merci

[Luc Hermitte]

Une collection qui exporte des itérateurs ?

Sinon, std::set n'est pas généralement implémenté comme un arbre binaire ?

[Laurent Gomila]

std::set est habituellement implanté sous forme d'arbre rouge et noir, ce qui est quand même un poil plus complexe que les arbres binaires classiques.

[Clad3]

hum, je ne connais pas encore les arbre rouge/noir, mais étant donné que ce sont des arbre je supose que le principe ne doit pas etre bien différent des AB et ABR, voir AVL .

Le probleme selon moi, n'est pas d'arrivé a implémenter ca, ( réinventer la roue n'est pas toujours la meilleur solution...surtout si on ne sais pas a quoi sert cette roue ... ) mais d'arriver a comprendre coment ca s'utilise et a quoi sa sert !

Une fois que tu sais ca, soit tu est assez bon en info pour pouvoir l'implementer de maniére efficace, soit tu le trouve deja tout fait .

hum sinon j'avais trouvé sur google un bon pdf ( cours de fac ) sur les ab/abr, avec implementation en c++ ... tu devrai pouvoir le retrouver

[SteelBox]

En fait, j'ai déjà implémenter un arbre binaire en C++ en cours. Mais je me demandais si la STL avait prévu quelque chose d'optimisée pour les arbres binaires, ce qui n'est apparement pas le cas...
Merci

[Laurent Gomila]

La STL ne possède rien de spécifique aux arbres (à part en interne), mais rien ne t'empêche de tout de même utiliser ses fonctions / classes pour faire du code propre et sûr 8).