Discussion :

[wafiwafi]

Bonjour à tous. Après avoir teminé la modélisation du fonctionnement d'un logiciel ( en utilisant UML), je réfléchis sur l'implémentation de ce dernier. Je voudrais utilser les arbres binaires de recherche ou les AVL. Ce choix est motivé par le fait que je serai amené à gérer des listes de clès qui sont très longues et donc ingérables un certain moment. Pour utiliser les arbres de recherche, on part d'une liste et on construit l'arbre qu'on met à jour au fûr et à mesure. Je dois également utiliser quelques arbres pour mémoriser des objets composites; ma question est donc :
Puis je construire un arbre de recherche à partir de l'arbre (structure de mémorisation) de départ? Est ce qu'il faut que je linéarise l'arbre initiale pour aboutir à une liste puis construire facilement l'arbre de recherche? si oui par quel parcours dois je le faire en infixe ou préfixe?
En fait, ce qui me manque, c'est des rappels concernant les différents contextes d'utilisation des arbres de recherche.
Merci à vous

[lysiandad]

A mon humble avis, les livres en ligne (C++/Java/C#) de Bruno R. Preiss sont parmi les incontournables à consulter, sur ces questions :

http://www.brpreiss.com/

Enjoy

'HTH

[wafiwafi]

Merci à vous.

[Hephaistos007]

En fait, ce qui me manque, c'est des rappels concernant les différents contextes d'utilisation des arbres de recherche.
Merci à vous

LA question fondamentale est : existe-t-il une relation d'ordre entre des clés ?

[wafiwafi]

les clés sont numériques; il ya donc forcément une relation d'ordre. Mais c'est vrai que je ne l'avais pas précisé.

[Hephaistos007]

Dans ce cas, tu peux les stocker dans un arbre binaire de recherche (ABR). A chaque nouvelle clé, tu l'insères dans l'arbre selon la procédure standard pour l'ajout d'un élément dans un ABR. Mais c'est surtout pour récupérer une clé que cela devient intéressant.

[wafiwafi]

OK Merci.
Es tu donc d'accord sur les interrogations que j'ai posées?

Pour rappel de mon message de départ :
Puis je construire un arbre de recherche à partir de l'arbre (structure de mémorisation) de départ? Est ce qu'il faut que je linéarise l'arbre initiale pour aboutir à une liste puis construire facilement l'arbre de recherche? si oui par quel parcours dois je le faire en infixe ou préfixe?


En fait je distingue deux choses: la structure de mémorisation et là je prendrai l'arbre binaire, et la façon avec laquelle je passe à l'arbre de recherche. Je sais que dans le cas d'une liste je construis directemnt l'arbre de recherche. Mais alors partant d'aun arbre, je ne sais pas. J'ai proposé une solution, mais je ne suis pas sûr.
Merci à toi.

[Hephaistos007]

A quoi te sert de stocker tes clés dans un arbre binaire au départ ?
Enfin soit, pour les transférer vers l'ABR, tu es obligé de les insérer un par un car c'est la procédure d'ajout dans un ABR qui calculera la position des clés dans l'ABR.