Algo - Parcours d'un arbre en largeur
Bonjour!
PROBLÈME
Comment fait - on le parcours en largeur d'un arbre binaire? (et de tout autre graphe)
RÉSOLUTION MANUELLE
imaginons un arbre
que donne le parcour en largeur?
(A) 20 (B) 10 30 (C)5 15 25 31 (D) 14 32
Que se passe-t'il? Par récurrence ou itération ça ne marche pas.
La difficulté est de garder le pointeur sur un noeud jusqu'à ce qu'on s'intéresse au fils du noeud.
Parce que par rapport à un parcours infixe par exemple le parcours en largeur donne l'impression de "remonter" dans l'arbre, or c'est impossible.
L'astuce est d'utiliser une file. (Comme les files d'attentes, premier arrivé = premier parti) first in first out en anglais (FIFO), par opposition à la pile (first in, last out, filo).
Que fait-on en vrai? j'enfile 20, je défile 20, et j'enfile ses fils 10 et 30, je défile 10 j'enfile 5 et 15, je défile 30 j'enfile RIEN et 31 je défile 5 et j'enfile RIEN et RIEN etc.. On se rend compte qu'on arrive à épuiser tous les noeuds du graphe.
ALGORITHME
c'est presque du C ou du java ;) mais comme je n'ai ni le temps ni l'envie d'écrire une structure pile en bonne et due forme. En se qui concerne les blocs de code je suggère de faire comme en python, et de se référer à l'indentation.
c'est clair comme ça?
COMPLÉXITE
On se rend compte que cet algorithme à un fâcheux défaut:
Il y a une file qui va réserver de l'espace mémoire pour s'exécuter. Intuitivement il nécessite beaucoup de mémoire (il faut pouvoir stocker un "étage" entier) alors que pendant un parcours préfixe/infixe/postfixé il suffit de stocker une hauteur (les noeuds entre la racine et le noeud courant).
Est le parcours en largeur d'un arbre binaire équilibré utilise vraiment plus d'espace qu'un parcours infixe?
Résonnons sur un arbre équilibré (AVL) de n noeuds (n non nul), la hauteur h (dans l'exemple le chemin de 20 à 14) est:
Si on considère la dernière ligne de notre AVL il y a k noeuds dans le pire des cas:
La dimension maximum dmax de la file est rencontrée à la fin de la lecture du dernier étage, ou celui juste avant (comme dans mon exemple) car l'étage h n'est pas toujours complet
finalement la file du parcours en largeur consomme plus de ressource que la pile du parcours infixe pour tous les graphes ayant nb noeuds, nb vérifiant
conclusion: pour un parcours en largeur il faut prévoir au pire des cas une hausse de 150 % de la mémoire utilisée, selon une règle linéaire, alors que le parcours infixe à un parcours logarithmique qui le rend beaucoup plus économe.
AVL: chaque noeud à autant de fils à droite et à gauche à un noeud près.
PROBLÈME
Comment fait - on le parcours en largeur d'un arbre binaire? (et de tout autre graphe)
RÉSOLUTION MANUELLE
imaginons un arbre
A +----------20----------+
| |
B +-----10-----+ +-----30-----+
| | | |
C 5 +--15 25 31--+
| |
D 14 32
que donne le parcour en largeur?
(A) 20 (B) 10 30 (C)5 15 25 31 (D) 14 32
Que se passe-t'il? Par récurrence ou itération ça ne marche pas.
La difficulté est de garder le pointeur sur un noeud jusqu'à ce qu'on s'intéresse au fils du noeud.
Parce que par rapport à un parcours infixe par exemple le parcours en largeur donne l'impression de "remonter" dans l'arbre, or c'est impossible.
L'astuce est d'utiliser une file. (Comme les files d'attentes, premier arrivé = premier parti) first in first out en anglais (FIFO), par opposition à la pile (first in, last out, filo).
Que fait-on en vrai? j'enfile 20, je défile 20, et j'enfile ses fils 10 et 30, je défile 10 j'enfile 5 et 15, je défile 30 j'enfile RIEN et 31 je défile 5 et j'enfile RIEN et RIEN etc.. On se rend compte qu'on arrive à épuiser tous les noeuds du graphe.
ALGORITHME
c'est presque du C ou du java ;) mais comme je n'ai ni le temps ni l'envie d'écrire une structure pile en bonne et due forme. En se qui concerne les blocs de code je suggère de faire comme en python, et de se référer à l'indentation.
/*declaration*/
noeud* tmp,suivant;
noeud* g = uneRacineArbre(graphe);
file* f = creerNouvelleFile();
/*initialisation*/
compteur registre= mettreAZero(creerNouveauCompteur());
enfiler(g,f);
/*la boucle principale, elle s'exécute jusqu'à ce que la file soit vide*/
tant que etreNonVide(f);
tmp = defiler(f);
/*en fonction du type de graphe le successeur s'écrit différemment*/
tant que suivant = successeur(tmp) et alors etreValable(suivant)
enfiler(suivant,f);
ecrireSortie(tmp);
/*on maintient un compteur sur le nombre de sommet (facultatif)*/
incrementer(registre);
renvoyer(registre);
c'est clair comme ça?
COMPLÉXITE
On se rend compte que cet algorithme à un fâcheux défaut:
Il y a une file qui va réserver de l'espace mémoire pour s'exécuter. Intuitivement il nécessite beaucoup de mémoire (il faut pouvoir stocker un "étage" entier) alors que pendant un parcours préfixe/infixe/postfixé il suffit de stocker une hauteur (les noeuds entre la racine et le noeud courant).
Est le parcours en largeur d'un arbre binaire équilibré utilise vraiment plus d'espace qu'un parcours infixe?
Résonnons sur un arbre équilibré (AVL) de n noeuds (n non nul), la hauteur h (dans l'exemple le chemin de 20 à 14) est:
h = PartieSup(ln(n)/ln(2));
la largeur l (la ligne C par ex) de hauteur i est, avec i=0 pour la racine:l=2^i
Interprétation: d'une ligne sur l'autre le nombre de noeuds double.Si on considère la dernière ligne de notre AVL il y a k noeuds dans le pire des cas:
k = 2^h
k = 2^(PartieSup(ln(n)/ln(2))) != x/2
(n-1)/2 < k <= n/2
k = 2^(PartieSup(ln(n)/ln(2))) != x/2
(n-1)/2 < k <= n/2
La dimension maximum dmax de la file est rencontrée à la fin de la lecture du dernier étage, ou celui juste avant (comme dans mon exemple) car l'étage h n'est pas toujours complet
dmax = Max(2^(h-1),nombre_noeud_etage(h))
Par simplification expresse:dmax = Max(n/2,nombre_noeud_etage(h))
finalement la file du parcours en largeur consomme plus de ressource que la pile du parcours infixe pour tous les graphes ayant nb noeuds, nb vérifiant
nb/2>ln(nb)/ln(2)
ce qui se vérifie à partir de 5conclusion: pour un parcours en largeur il faut prévoir au pire des cas une hausse de 150 % de la mémoire utilisée, selon une règle linéaire, alors que le parcours infixe à un parcours logarithmique qui le rend beaucoup plus économe.
AVL: chaque noeud à autant de fils à droite et à gauche à un noeud près.