ARBRES N-ARIES
Bacterius
Messages postés
3792
Date d'inscription
samedi 22 décembre 2007
Statut
Membre
Dernière intervention
3 juin 2016
-
26 juil. 2010 à 16:17
cs_Kagemaru Messages postés 6 Date d'inscription dimanche 6 décembre 2009 Statut Membre Dernière intervention 2 mai 2014 - 11 août 2010 à 01:04
cs_Kagemaru Messages postés 6 Date d'inscription dimanche 6 décembre 2009 Statut Membre Dernière intervention 2 mai 2014 - 11 août 2010 à 01:04
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/52087-arbres-n-aries
https://codes-sources.commentcamarche.net/source/52087-arbres-n-aries
11 août 2010 à 01:04
10 août 2010 à 21:08
Par exemple, je veux créer un arbre... (tiens donc, quelle idée !) qui puisse être un arbre d'Entiers, de records ou d'objets.
Je vais donc créer une classe (dans cet exemple avec les génériques, c'est plus pratique) comme ceci :
TNode<T> = class;
TNodes<T> = array of TNode<T>
TNode<T> = class
public
Value : T;
Parent : TNode<T>;
ChildNumber : Integer;
Children : TNodes<T>;
end;
// Et pour le destructeur on aurait (par exemple)
destructor TNode<T>.Destroy;
var
NumChild : Integer;
begin
for NumChild := 0 to CountChildren - 1 do
Children[NumChild].Free;
end;
Bien, c'est cool ça mais on en fait quoi ? Et c'est quoi T ?
Alors là, si on veut par exemple créer un noeud avec une valeur Integer, on va faire :
var
Node : TNode;
begin
Node := TNode.Create;
end;
En fait, à la compilation, T sera remplacé par ce que l'on a choisi au sein de l'instance créée.
Il s'agit en fait d'un simple paramètre formel.
Car lorsque l'on déclare Node : TNode, le compilateur va le comprendre comme si on écrivait : Node : TIntegerNode;
avec
TIntegerNode = class;
TIntegerNodes = array of TIntegerNode
TIntegerNode = class
public
Value : Integer;
Parent : TIntegerNode;
ChildNumber : Integer;
Children : TIntegerNodes;
destructor Destroy; override;
// Pas mal d'autres fonctions...
end;
Donc un peut créer des arbres de n'importe quoi sans avoir à changer le code de la class.
Enfin (et c'est là que la class va devenir importante), il y a plusieurs types de noeuds : les noeuds de record, d'entier, etc, et les noeuds d'objets.
L'avantage des records, entiers etc, c'est que leur libération est automatique lorsque l'on appelle le Node.Free;
Pas pour les objets.
Donc comment faire ? Car l'exemple précédent ne détruit pas l'éventuel objet pointé par Value dans le destructeur.
Ici, on va créer une classe qui héritera de TNode<T>, qui sera
TObjectNode<T : class> = class(TNode<T>)
public
destructor Destroy; override;
end;
destructor TObjectNode<T>.Destroy;
begin
inherited;
Value.Free;
end;
Tu remarqueras qu'ici, on indique dans le type générique "T : class". C'est à dire que T ne pourra pas être un type Integer, Real, String, record, etc... Il faudra que se soit un objet. Cependant, ceci nous permet d'appeler Value.Free, ce qui sera impossible si on ne savait pas que Value était un objet (on ne peut pas faire de Free sur un Integer par exemple).
Voilà, à peu près ce que c'est les génériques.
C'est pas trop trop difficile à utiliser même si je pense qu'il y a deux écueils à éviter : Le premier c'est de trop les utiliser, d'une part ça complique le code et d'autre part c'est pas forcément le meilleur moyen (parfois un simple paramètre "class of ..." peut suffire, ou même, il est souvent aussi pratique de mettre un simple TObject lorsque c'est possible). Le deuxième n'est pas vraiment un écueil, mais il s'agit d'une mise en garde. Le comportement des génériques est parfois surprenant... Cela vient certainement du fait que je ne les maîtrise pas totalement, mais j'ai déjà eu des bugs très étranges avec des programmes très simple employant les génériques.
Pour conclure, les génériques, c'est vraiment super pratique mais c'est pas automatique ;). Je te conseille donc vivement de te documenter à propos d'eux car ce sont des outils puissants mais pas toujours facile à appréhender (comme l'interaction entre générique et constructeur...).
Et comme on apprend beaucoup plus par l'exemple, je te conseille de regarde l'unité Generics.Collections et, pour commencer, les classes TStack<T> et TObjectStack<T> sans te préoccuper de TEnumerable<T> et TEnumerator<T>.
Plus généralement, je te conseille de bien comprendre l'unité Generics.Collections qui est une mine de petites merveilles (notamment la très pratique TObjectList<T> qui te permet d'éviter tous les transtypages que l'on connaît avec la version classique Contnrs.TObjectList).
A bientôt
10 août 2010 à 17:28
Merci pour l'aide, moi aussi je suis du genre borné mais pas cette fois, parle moi plutôt de Generics?
J'utilise Delphi 2009.
@+
10 août 2010 à 15:05
Il faut savoir que je suis du genre un peu borné, donc je vais développer quelques arguments supplémentaires... :
1) Je suis d'accord avec toi, c'est un peu plus souple mais c'est aussi et surtout beaucoup plus dangereux (au niveau des ressources mémoires). De plus, je trouve cela dommage de ne pas utiliser les classes de Delphi préexistantes (j'ai d'ailleurs fait récemment des découvertes très utiles en passant à RAD Studio 2010 avec les classes Generics.Collections et Generics.Default). Et enfin, pour moi, Delphi, c'est ça! L'objet! je laisse le reste au C et au Pascal...
2) EN fait, l'avantage de la classe TList est qu'elle ne redimensionne pas le tableau à chaque appel de Add ou de Insert. Il y a une variable Capacity et une fonction Grow qui permet de prévoir un peu plus que nécessaire (pour anticiper les prochains éventuels redimensionnements). C'est cela qui fait toute ça force. Il n'y a qu'à comparer, une très simple comparaison des deux Add (l'un avec TList, l'autre avec Tableau Dynamique) me donne 150 ms pour le premier et 400 ms pour le second (pour 10 000 000 d'appel à Add).
3) Enfin, quelques modifications.
// On utilise le maximum
function TreeHeight(Tree : PNode) : integer;
var I : integer;
begin
if Tree = nil then
begin
Result := 0;
Exit;
end;
if CountChildren(Tree) = 0 then
Result := 1
else
begin
Result := T[0];
for I := 1 to CountChildren(Tree) - 1 do
Result := Max(Result, TreeHeight(Tree.Children[I]));
Result := 1 + Result;
end;
end;
// Pas besoin de faire Node^.Children := nil car on libère la mémoire allouée à Node juste après donc, ça valeur, on s'en balance.
procedure Free(var Node : PNode; FreeValueProc : TFreeValueProc);
begin
if Assigned(FreeValueProc) then
FreeValueProc(Node^.Value);
SetLength(Node^.Children, 0);
Dispose(Node)
end;
// Moins de conditions et certainement plus juste (tu oubliais de libérée la mémoire allouée à l'arbre lui même)
procedure DestroyTree(var Tree : PNode; FreeValueProc : TFreeValueProc);
var I : integer;
begin
if Tree = nil then
Exit;
for I := 0 to CountChildren(Tree) - 1 do
DestroyTree(Tree.Children[I], FreeValueProc);
Free(Tree, FreeValueProc);
end;
Je n'ai pas testé cette unité, un exemple serait effectivement le bienvenu. Mais je pense ne pas avoir fait de catastrophes dans les modifications (ensuite je crois un peu ce que je veux...).
Une dernière chose : Quelle version de Delphi utilises-tu ? Car je pense que dans ton cas, la souplesse que tu recherche pour ton Arbre c'est utiliser une Value qui peut être un objet ou un record ou n'importe quoi d'autre. Si tel est le cas, la bonne solution pourrait être d'utiliser les génériques (merveilleuse petite bête une fois adoptée bien qu'il faille les manipuler avec précaution).
A bientôt
10 août 2010 à 13:57
Merci pour ton commentaire,
1) J'ai pas utilisé une structure objet pour la raison que vous venez de dire : tout dépend de l'utilisation, pour rendre l'arbre plus dynamique(souple à utiliser) le mieux possible.
2) "l'utilisation du SetLength à outrance n'est pas nécessairement très bon" je ne partage pas votre opinion. Et même si tu regardes à TList comment il est fait tu verras que c'est un tableau statique c'est pas totalement dynamique.
3) Vous avez raison en ce qui concerne la maximum. En effet TreeHeight et DestroyTree ne fonctionnent pas correctement si vous des suggestions.
Merci.
10 août 2010 à 12:06
Pourquoi n'utilises-tu pas une structure orientée objet ?
De plus, l'utilisation de TList à la place d'un tableau pour les nœuds enfants simplifierait grandement le code (les fonctions insertions, d'ajout et de suppression, ainsi que la fonction QuickSort seraient supprimés!)
En fait, trois choses me dérange dans cette unité :
- d'une part, comme je l'ai dit, il serait peut être préférable d'adopter une structure objet. Mais, ici, tout dépend de l'utilisation que l'on en fait. Peux-tu d'ailleurs expliquer ce choix?
- d'autre part, l'utilisation du SetLength à outrance n'est pas nécessairement très bon. Il est dès lors préférable d'utiliser une liste (TList ou TObjectList) qui ne redimensionne pas le tableau de pointeurs à chaque appel de Add.
- enfin. Pourquoi utiliser un algorithme de QuickSort (en O(n ln(n)) ) dans TreeHeight alors qu'une simple recherche de maximum suffit (en O(n)).
Sinon, le code est plutôt clair et bien présenté.
29 juil. 2010 à 21:37
29 juil. 2010 à 18:45
Bien à toi
Jean_jean
29 juil. 2010 à 17:17
C'est par hasard que je tombe sur ton code!
Je suis en plein dedans car je vais en avoir besoin dans un projet!
En ce moment, je développe un composant pour tracer justement les B-Arbres. J'ai quelques soucis de graphisme, si ça t'intéresse, nous pourrions collaborer à ce développement.
Je n'ai pas le temps de vérifier ton code maintenant, mais je reviendrai vers toi pour te faire part de mes commentaires. j'avais approfondi cette question du temps du Turbo-pascal et des débuts de Delphi, alors il faut que je remette à jour.
A première vue, tu as juste développé les fonctions de base. C'est bien, mais la gestion d'un arbre n-aire est délicat pour des raisons de déséquilibre des branches au fur et à mesure de son utilisation.
A+
26 juil. 2010 à 16:17
je n'ai pas tout lu le code mais je m'active dessus, toutefois pourrais-tu inclure un petit exemple (pas très compliqué) d'une utilisation possible de cette source ? Par exemple, pourquoi pas faire une petite source qui indexe un dossier au choix, avec les sous-dossiers, dans un arbre n-aire, puis qui affiche le résultat dans un TTreeView ?
Cordialement, Bacterius !