Epita:Algo:Cours:Info-Sup

De EPITACoursAlgo.
(Différences entre les versions)
(les structures arborescentes)
(les structures arborescentes)
Ligne 18 : Ligne 18 :
  
 
Les arbres se rencontrent à la base sous deux formes : [[Epita:Algo:Cours:Info-Sup:Structures arborescentes|les ''arbres binaires'' et les ''arbres généraux'']].
 
Les arbres se rencontrent à la base sous deux formes : [[Epita:Algo:Cours:Info-Sup:Structures arborescentes|les ''arbres binaires'' et les ''arbres généraux'']].
 
Les arbres binaires
 
 
La définition récursive d’un arbre binaire est B=< o, B1, B2> où o est le nœud racine, et B1 et B2 sont deux arbres binaires disjoints. Un arbre binaire vide est représenté par .
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figure 1. Représentation graphique d’un arbre binaire
 
 
Pour cet exemple, nous avons associé à chaque nœud un numéro pour pouvoir les distinguer les uns des autres. Une chose importante à remarquer est la non symétrie d’un arbre binaire.
 
Le type abstrait d’un arbre binaire est le suivant :
 
 
SORTE
 
ArbreBinaire
 
 
UTILISE
 
Noeud, Elément
 
 
OPERATIONS
 
Arbre-vide :  ArbreBinaire
 
< _,_,_ > : Nœud x ArbreBinaire x ArbreBinaire  ArbreBinaire
 
racine : ArbreBinaire  Noeud
 
 
g : ArbreBinaire  ArbreBinaire
 
d : ArbreBinaire  ArbreBinaire
 
contenu : Noeud  Elément
 
 
PRECONDITIONS
 
racine(B) est-défini-ssi BArbre-vide
 
g(B) est-défini-ssi BArbre-vide
 
d(B) est-défini-ssi BArbre-vide
 
 
AXIOMES
 
racine (<o,B1,B2>)=o
 
g(<o,B1,B2>)=B1
 
d(<o,B1,B2>)=B2
 
 
AVEC
 
o : Noeud
 
B,B1,B2 : ArbreBinaire
 
 
Terminologie
 
 
La manipulation des arbres binaires nécessite l’utilisation d’un vocabulaire approprié dont voici les principaux éléments :
 
 
Soit un arbre binaire B=<o,B1,B2>
 
 
 o est la racine de B
 
 B1 est le sous-arbre gauche de B
 
 B2 est le sous-arbre droit de B
 
 La racine du sous-arbre gauche (sous-arbre droit) d’un nœud est son fils gauche (fils droit)
 
 Le lien entre un nœud et son fils gauche (fils droit) est appelé lien gauche (lien droit)
 
 Un nœud ni (seulement quand il approche de l’écurie) ayant pour fils gauche (fils droit) un nœud nj est appelé père de nj
 
 Deux nœuds de même père sont dits frères
 
 Un nœud ni est appelé ascendant (descendant) d’un nœud nj si, et seulement si, ni est le père (fils) de nj ou un ascendant (descendant) du père (fils) de nj
 
 Les nœuds d’un arbre binaire ont au plus deux fils
 
 Un nœud ayant deux fils est appelé nœud interne ou point double
 
 Un nœud n’ayant qu’un fils gauche (fils droit) est appelé point simple à gauche (point simple à droite), ou nœud interne au sens large
 
 Un nœud n’ayant pas de fils est appelé nœud externe ou feuille
 
 Tout chemin allant de la racine de B à une feuille de B est appelé branche de B
 
 Un arbre binaire possède autant de branches que de feuilles
 
 Le chemin obtenu en partant de la racine et ne suivant que des liens gauches (liens droits) est appelé bord gauche de B (bord droit de B)
 
 
Remarques diverses : Contrairement à la vraie vie, les arbres binaires ne présentent pas de variétés à feuillage persistant ou caduque. Quand je veux supprimer une feuille, je le fais. Mais le plus fort, c’est que j’en crée une (de feuille) quand je veux. On oubliera aussi les notions familiale de cousinage et autres.
 
Mesures sur les arbres binaires
 
 
Nous allons voir maintenant des opérations sur les arbres qui vont nous permettrent de prendre diverses mesures et de pouvoir alors déterminer la complexité des différents algorithmes qui leur sont appliqués (aux arbres évidemment, de quoi on parle là ?). Ces opérations sont les suivantes :
 
 
 La taille d’un arbre correspond au nombres de ses nœuds, elle est définie par :
 
T(arbre-vide)=0
 
T(B=<o,B1,B2>)=1+T(B1)+T(B2)
 
 La hauteur, profondeur ou niveau d’un nœud est définie comme suit : soit un nœud x d’un arbre B, on a :
 
H(x)=0 si x est la racine de B
 
H(x)=1+H(y) si y est le père de x
 
 La hauteur, profondeur d’un arbre B est  définie par :
 
H(B)=max{H(x) ; x nœud de B}
 
 La longueur de cheminement d’un arbre B est définie par :
 
LC(B)=H(x) ;x nœuds de B
 
 La longueur de cheminement externe d’un arbre B est définie par :
 
LCE(B)=H(f) ;f feuilles de B
 
 La longueur de cheminement interne d’un arbre B est définie par :
 
LCI(B)=H(x) ;x nœuds internes de B
 
 
On a alors la relation : LC(B)=LCE(B)+LCI(B)
 
 
 La profondeur moyenne interne d’un arbre B est définie par :
 
PMI(B)=LCI(B)/Nbi ;Nbi nombre de nœuds internes de B
 
 La profondeur moyenne externe d’un arbre B est définie par :
 
PME(B)=LCE(B)/Nbf ;Nbf nombre de feuilles de B
 
 La profondeur moyenne  d’un arbre B est définie par :
 
PM(B)=LC(B)/T(B)
 
 
Caractéristiques des nœuds (appliqué à l’exemple de la Figure 1) :
 
 
 n1 est la racine de B
 
 n2 est son fils gauche et n3 son fils droit
 
 n5 et n6 sont frères
 
 n1, n3, n4 et n8 sont des points doubles
 
 n2 est un point simple à gauche
 
 n6 est un point simple à droite
 
 n5, n7, n9, n10 et n11 sont des feuilles
 
 (n1, n2, n4, n7) est le bord gauche
 
 (n1, n3, n6, n9) est le bord droit
 
 (n1, n2, n4, n8, n10) est une branche de B
 
 Hauteurs :
 
 H(n1)=0
 
 H(n2)=H(n3)=1
 
 H(n4)=H(n5)=H(n6)=2
 
 H(n7)=H(n8)=H(n9)=3
 
 H(n10)=H(n11)=4
 
 
Caractéristiques de l’arbre :
 
 
 Hauteur :
 
 H(B)=4
 
 Taille :
 
 T(B)=11
 
 Longueur de cheminement :
 
 LC(B)=25
 
 LCI(B)=9
 
 LCE(B)=16
 
 Profondeur moyenne :
 
 PM(B)=25/11  2,272
 
 LCI(B)=9/6  1,5
 
 LCE(B)=16/5  3,2
 
 
Arbres binaires particuliers
 
 
Il existe des formes particulières d’arbres binaires qu’il faut connaître dans la mesure où leur spécificité permet de modifier les algorithmes sur les arbres, voire d’utiliser des algorithmes propres à leur structure.
 
Ces arbres présentés en figure 2 sont :
 
 
 Dégénérés ou filiformes
 
 Complets
 
 Parfaits
 
 Localement complets
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figure 2. Arbres binaires particuliers
 
 
 Les arbres dégénérés Figure 2 (a) ne sont constitués que de points simples à gauche ou à droite.
 
 Les arbres complets Figure 2 (b) voient tous leurs niveaux remplis
 
 Les arbres parfaits Figure 2 (c) voient tous leurs niveaux remplis excepté le dernier qui a toutes ses feuilles ramenées complètement à gauche.
 
 Les arbres localement complets Figure 2 (d) ne sont constitués que de points doubles et de feuilles. On peut constater sur la Figure 2 (e) une particularité des arbres localement complets, le peigne droit dont tous les fils gauches sont des feuilles. Il existe bien sûr le peigne gauche.
 
 
Occurrence et numérotation hiérarchique
 
 
Une façon de décrire un arbre binaire est de lui associer un mot formé de 0 et de 1. Ce mot est appelé occurrence du nœud. Par définition, la racine d’un arbre est noté  et si un nœud a pour occurence  alors, son fils gauche à pour occurrence 0 et son fils droit 1. Pour l’arbre de la figure 1, nous aurions alors :
 
 
B={, 0, 1, 00, 10, 11, 000, 001, 111, 0010, 0011}
 
 
D’autre part, les nœuds peuvent être numérotés de façon hiérarchique. C’est à dire qu’au lieu, comme sur la figure 1, de les numéroter par niveau, si l’on a un nœud ni alors son fils gauche sera le nœud n2i et son fils droit le nœud n2i+1. Ce qui pour l’exemple de la figure 1 donnerait :
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figure 3. Numérotation hiérarchique
 
 
Nous verrons plus loin que cette numérotation présente, entre autres, un intérêt sur certains arbres lors d’une représentation statique.
 
 
 
Représentation des arbres binaires
 
 
Comme pour les structures séquentielles, nous avons la possibilité de représenter les arbres en mémoire sous forme dynamique ou sous forme statique. Cette dernière pouvant être utilisée pour simuler la première.
 
 
Représentation dynamique
 
 
Cette représentation est un quasi calque de la structure d’un arbre binaire. Chaque Nœud contient un élément (l’étiquette) et deux liens : un vers le fils gauche et l’autre sur le fils droit. Ce qui donne :
 
 
Types
 
Element = …. /* Définition du type des éléments */
 
T_Arbre =  T_Noeud /* type pointeur sur T_Noeud * /
 
 
T_Noeud  = Enregistrement
 
Element Elt
 
T_Arbre Fg,fd
 
Fin Enregistrement T_Noeud
 
Variables
 
T_Arbre B
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figure 4. Représentation dynamique d’un arbre binaire.
 
Dans ce type de représentation (adaptation en figure 4 de l’arbre donné en figure 3), les correspondances entre les opérations abstraites et l’implémentation dynamique du type sont les suivantes :
 
 
 B=Arbre-vide  B=nul
 
 B< _, _, _>  Allouer(B)
 
 racine(B)  B
 
 g(B)  B.fg
 
 d(B)  B.fd
 
 Contenu(racine(B))  B.Elt
 
 
Représentation statique
 
 
Dans cette représentation, l’arbre sera contenu dans un vecteur (tableau à une dimension) d’enregistrements contenant chacun 3 champs : l’élément et deux entiers (un pour le fils gauche et l’autre pour le fils droit). Ces derniers (les deux entiers) référençant dans le vecteur l’indice du fils concerné (Suis-je assez clair ?). La base du Vecteur étant 1, nous pouvons utiliser 0 comme référence de pointeur nul (l’arbre vide, quoi ?!). De plus, il nous faut la position de la racine donnée par un entier.
 
 
Remarque : Lors d’une implémentation en C, il faudra alors utiliser –1, la base étant 0.
 
 
Ceci étant voilà la déclaration algorithmique d’une telle structure :
 
 
Constante
 
Nbmax = 8
 
Type
 
Element = …. /* Définition du type des éléments */
 
T_Nœud = Enregistrement
 
Element Elt
 
Entier fg, fd
 
Fin Enregistrement T_Noeud
 
T_VectNbmaxNoeud  =  Nbmax T_Noeud
 
T_Arbre = Enregistrement
 
T_VectNbmaxNoeud Noeuds
 
Entier Racine
 
Fin Enregistrement T_Arbre
 
Variable
 
T_Arbre B
 
 
Dans ce type de représentation, les correspondances entre les opérations abstraites et l’implémentation statique du type sont les suivantes :
 
 
 B=Arbre-vide  B.racine=0
 
 racine(B)  B.racine
 
 g(B)  B.Nœuds(B.racine).fg
 
 d(B)  B.Nœuds(B.racine).fd
 
 Contenu(racine(B))  B.Nœuds(B.racine).Elt
 
Adaptée à l’arbre de la figure 1, nous aurions le tableau présenté en Figure 5. En fait, dans ce type d’arbre, la racine peut être située à n’importe quel indice. Ce qui fait que l’on peut représenter dans un même tableau plusieurs arbres en même temps, une forêt par exemple ( Et là, je suis très sérieux.). Il suffit simplement de maîtriser pour chacun la position de sa racine.
 
 
Elt fg Fd
 
1 n1 2 3
 
2 n2 4 0
 
3 n3 5 6
 
4 n4 7 8
 
5 n5 0 0
 
6 n6 0 9
 
7 n7 0 0
 
8 n8 10 11
 
9 n9 0 0
 
10 n10 0 0
 
11 n11 0 0
 
12
 
 
Figure 5. Représentation statique d’un arbre binaire.
 
 
Elt fg fd Elt
 
1 n1 2 3 1 n1
 
2 n2 4 0 2 n2
 
3 n3 6 7 3 n3
 
4 n4 8 9 4 n4
 
5 5
 
6 n6 0 0 6 n6
 
7 n7 0 15 7 n7
 
8 n8 0 0 8 n8
 
9 n9 18 19 9 n9
 
10 10
 
11 11
 
12 12
 
13 13
 
14 14
 
15 n15 0 0 15 n15
 
16 16
 
17 17
 
18 n18 0 0 18 n18
 
19 n19 0 0 19 n19
 
20 20
 
 
a b
 
 
Figure 6. Représentation statique d’un arbre binaire numéroté hiérarchiquement.
 
D’autre part, si nous avions utilisé, pour le même arbre, une numérotation hiérarchique comme en figure 3, nous aurions obtenu le tableau suivant (Figure 6a):
 
 
Comme on peut le constater sur la figure 6a, cette numérotation présente deux défauts majeurs :
 
 
 Elle nous oblige à fixer la racine d’un arbre non vide en indice 1
 
 Elle génère des trous dans le tableau et par conséquent un taux d’occupation assez faible.
 
 
Cela dit, elle est idéale pour les arbres complets ou parfaits dans la mesure où, pour ceux-ci tous les niveaux, sauf éventuellement le dernier, sont remplis, donc pas de trous (Golfeurs du Monde, Désolé !).
 
 
De plus, un nœud ni ayant pour fils gauche un nœud n2i et pour fils droit un nœud n2i+1, nous n’avons plus besoin de référencer le fils gauche et le fils droit. Ce qui permet de représenter l’arbre à l’aide d’un simple vecteur d’éléments comme montré sur la figure 6b.
 
 
Remarque : Il faut trouver un moyen à l’aide de l’élément pour référencer un arbre vide (la racine à 0, par exemple).
 
 
Remarque 2 : Cette représentation permet, sans avoir à le mémoriser, de connaître le père d’un nœud. Il suffit pour un nœud ni avec i >1 de rechercher le nœud ni div 2 .
 
 
Remarque 3 : Nous sommes toujours tenus d’avoir une racine en 1 pour un arbre non vide.
 
 
Pour ce type de représentation (figure 6b), la déclaration algorithmique deviendrait :
 
 
Constante
 
Nbmax = 8
 
Type
 
Element = …. /* Définition du type des éléments */
 
T_VectNbmaxNoeud  =  Nbmax Element
 
T_Arbre = Enregistrement
 
T_VectNbmaxNoeud Noeuds
 
Entier Racine
 
Fin Enregistrement T_Arbre
 
Variable
 
T_Arbre B
 
 
Et les correspondances entre les opérations abstraites et l’implémentation statique du type seraient les suivantes :
 
 
 B=Arbre-vide  B.racine=0
 
 racine(B)  B.racine
 
 g(B)  B.Nœuds(2*B.racine)
 
 d(B)  B.Nœuds(2*B.racine+1)
 
 Contenu(racine(B))  B.Nœuds(B.racine)
 
 
Parcours d’un arbre binaire
 
 
De nombreux algorithmes sur les arbres examinent systématiquement tous les nœuds d’un arbre pour y effectuer un traitement particulier. Cette opération s’appelle le parcours d’un arbre. Il existe plusieurs formes de parcours d’arbre : le parcours en largeur (Aaaahh…)et le parcours en profondeur (Ooohh…).
 
Le premier consiste à passer en revue tous les nœuds niveau par niveau. Le deuxième consiste à étudier les nœuds en descendant à chaque fois le plus loin possible dans l’arbre. Nous n’allons présenter que le parcours en profondeur. Celui-ci sera une forme dérivée des sorties labyrinthiques. C’est à dire que l’on pose sa main gauche sur un mur, et que l’on avance en laissant celle-ci posée. Dans la plupart des cas (Franquin et ses idées noires vous en fourniront un autre), nous arriverons fatalement à la sortie. Cette forme dérivée de parcours sur les arbres binaires s’appelle le parcours en profondeur main gauche.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figure 7. Parcours profondeur main gauche d’un arbre binaire
 
 
Sur le parcours de la Figure 7, nous n’avons pas représenté les sous-arbres vides, mais ceux-ci doivent être pris en compte si l’on veut admettre que chaque nœud est rencontré trois fois lors du parcours (Figure 8) :
 
 
 à la descente vers le sous-arbre gauche,
 
 au passage du sous-arbre gauche vers le sous-arbre droit
 
 à la remontée depuis le sous-arbre droit.
 
 
 
 
 
 
 
 
 
 
Figure 8. Rencontres d’un Nœud pendant un parcours
 
 
Algorithme de parcours profondeur main gauche
 
 
Lors du parcours, chaque nœud étant rencontré trois fois, nous pouvons affecter à chacun d’eux un traitement particulier. De plus, si l’on intègre les arbres vides, nous pouvons aussi y faire correspondre un traitement. Ce qui donne l’algorithme abstrait suivant, de parcours récursif d’un arbre :
 
 
Algorithme procedure parcours
 
Paramètres locaux
 
Arbre B
 
Debut
 
Si B=arbre-vide alors
 
TERMINAISON /* traitement de terminaison */
 
Sinon
 
TRT1 /* traitement 1 (préfixe) */
 
parcours(g(B))
 
TRT2 /* traitement 2 (infixe) */
 
parcours(d(B))
 
TRT3 /* traitement 3 (postfixe) */
 
Fin si
 
Fin algorithme procedure parcours
 
 
Pour bien mettre en évidence les différences entre les trois ordres induits par ce parcours, nous allons remplacer à chaque fois chacun d’eux par un ordre d’affichage du nœud (Ecrire(contenu(racine(B))). Les autres traitements étant vides. Voilà ce qui serait obtenu à chaque fois si l’on appliquait cet algorithme de parcours à l’arbre binaire de la figure 7 :
 
 
(a) ordre préfixe (Figure 8 (a)). n1, n2, n4, n7, n8, n10, n11, n3, n5, n6, n9
 
 
(b) ordre infixe (Figure 8 (b)). n7, n4, n10, n8, n11, n2, n1, n5, n3, n6, n9
 
 
(c) ordre postfixe (Figure 8 (c)). n7, n10, n11, n8, n4, n2, n5, n9, n6, n3, n1
 
 
On constate que selon le type de parcours l’ordre des nœuds diffère (Fer !).
 
 
Remarque 1: L’ordre hiérarchique n’apparaît pas dans la mesure où celui-ci correspond à un parcours en largeur (par niveau) de l’arbre.
 
 
Remarque 2 : Tous les traitements peuvent être utilisés en même temps pour, éventuellement, réaliser des choses diverses dans un ordre différent, ou alors parce que ces traitements sont complémentaires. Nous allons voir dans le paragraphe suivant la nécessité d’utiliser plusieurs de ces traitements.
 
 
Parcours d’un arbre étiqueté représentant une expression arithmétique
 
 
Nous pouvons utiliser un arbre binaire pour représenter une expression arithmétique. Dans ce cas, les nœuds internes sont les opérateurs et les feuilles sont les opérandes. Ce qui, pour l’expression arithmétique (a+((b*4)/3)),pourrait donner :
 
 
 
 
 
 
 
 
 
 
 
 
 
Figure 9. Arbre binaire étiqueté représentant une expression arithmétique
 
 
Remarque : Cette expression n’utilise que des opérateurs binaires (ayant deux opérandes), il est donc localement complet.
 
 
Pour l’arbre de la figure 9, le parcours selon les différents ordres donnerait :
 
 
(a) ordre préfixe. + a / * b 4 3
 
 
(b) ordre infixe. a + b * 4 / 3
 
 
(c) ordre postfixe . a b 4 * 3 / +
 
 
On constate que l’ordre préfixe et l’ordre postfixe sont non ambiguës, le premier correspondant à une notation en polonaise et le deuxième à une notation en polonaise inversée. Ce n’est malheureusement pas le cas de l’ordre infixe pour qui cette série pourrait correspondre à un autre arbre donné en figure 10.
 
En effet les notations en polonaise ou en polonaise inversée font précéder ou suivre les opérateurs de leurs opérandes. Or pour la notation en ordre infixe, nous ne savons pas si a+b*4 correspond à (a+b)*4 ou à a+(b*4) . En fait cette ambiguïté peut être levée à l’aide de parenthèses qui forceraient alors la priorité des opérateurs.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figure 10. Arbre binaire étiqueté représentant une expression arithmétique
 
donnant le même parcours infixe que celui de la figure 9.
 
Il suffit alors de modifier l’algorithme de parcours en profondeur main gauche donné précédemment de la manière suivante :
 
 
Algorithme procedure parcoursinfixe
 
Paramètres locaux
 
Arbre B
 
Debut
 
Si (g(B)=arbre-vide) et (d(B)=arbre-vide) alors /* feuille */
 
Ecrire(contenu(racine(B))) /* traitement de terminaison */
 
Sinon
 
Ecrire (‘(‘) /* traitement 1 (préfixe) */
 
parcours(g(B))
 
Ecrire(contenu(racine(B))) /* traitement 2 (infixe) */
 
parcours(d(B))
 
Ecrire (‘)’) /* traitement 3 (postfixe) */
 
Fin si
 
Fin algorithme procedure parcoursinfixe
 
 
Ce qui pour les arbres donnés en figure 9 et en figure 10 donnerait :
 
 
 Figure 9. (a+((b*4)/3))
 
 Figure 10. (a+(b*(4/3)))
 
 
Remarque : Dans l’algorithme, nous aurions pu modifier le test qui vérifie si le nœud sur lequel nous sommes est une feuille. Pour cela, il aurait fallu faire une extension au type abstrait ArbreBinaire en créant une nouvelle opération comme suit :
 
 
OPERATIONS
 
feuille : ArbreBinaire  Booléen
 
 
AXIOMES
 
feuille(B)=Vrai  Barbre-vide & g(B)=arbre-vide & d(B)=arbre-vide
 
 
Le début de l’algorithme serait alors :
 
 
Algorithme procedure parcoursinfixe
 
Paramètres locaux
 
Arbre B
 
Debut
 
Si feuille(B) alors /* feuille */
 
 
Les arbre généraux
 
 
Un arbre général ou arbre est une structure arborescente où le nombre de fils n’est pas limité à deux. La définition récursive d’un arbre général est A=< o, A1,  …, An > où A est la donnée d’une racine o et d’une liste finie, éventuellement vide, d’arbres disjoints. On appelle cette liste une forêt (Alors, hein ? On ne me croyait pas !). On obtient donc un arbre en ajoutant une racine à une forêt (Ca tombe sous le sens).
 
 
 
 
 
 
 
 
 
 
 
 
 
Figure 11. Représentation graphique d’un arbre général.
 
 
Le type abstrait d’un arbre général est le suivant :
 
 
SORTE
 
Arbre, Forêt
 
 
UTILISE
 
Noeud, Entier
 
 
OPERATIONS
 
cons : Noeud x Forêt  Arbre
 
racine : Arbre  Noeud
 
liste-arbre : Arbre  Forêt
 
forêt-vide :  Forêt
 
ième : Forêt x Entier  Arbre
 
nb-arbres : Forêt  Entier
 
insérer : Forêt x Entier x Arbre  Forêt
 
 
PRECONDITIONS
 
insérer(F,i,A) est-défini-ssi 1i1+nb-arbres(F)
 
 
AXIOMES
 
racine(cons(o,F))=o
 
liste-arbre(cons(o,F))=F
 
nb-arbres(forêt-vide)=0
 
1i1+nb-arbres(F)  nb-arbres(insérer(F,i,A))=nb-arbres(F)+1
 
1k<i  ième(insérer(F,i,A),k)=ième(F,k)
 
k=i  ième(insérer(F,i,A),k)=A
 
i+1k1+nb-arbres(F)  ième(insérer(F,i,A),k)=ième(F,k-1)
 
 
AVEC
 
o : Noeud
 
F : Forêt
 
A : Arbre
 
i,k : Entier
 
 
Remarque : La notion de « gauche-droite » propre aux arbres binaires disparaît. Cela dit, le vocabulaire employé pour les arbres généraux reste le même hormis pour tout ce qui fait appel à cette notion (de généralité). Par exemple, on ne parle plus de fils gauche-fils droit, mais de 1er fils, 2ème fils, etc. et de dernier fils.
 
 
Remarque 2 : Les mesures sur les arbres sont conservées (hauteur, longueur de cheminement, taille, etc.).
 
 
Représentation des arbres généraux
 
 
Il existe plusieurs formes de représentations des arbres généraux. Les plus intuitives sont la représentation sous forme de listes chaînées et n-uplet. Une autre forme très usitée est la représentation sous forme d’arbres binaires.
 
 
Représentation sous forme statique-dynamique
 
 
Dans ce cas de figure, l’ensemble des nœuds est représenté dans un tableau à une dimension (vecteur) surdimensionné pour pouvoir y ajouter des nœuds le cas échéant. Chaque élément est un enregistrement qui contient l’étiquette du nœud plus un pointeur sur sa liste de fils. La liste de fils est composée d’enregistrements contenant un pointeur sur le type d’élément constituant le tableau et un pointeur suivant. Dans ce cas, sa description algorithmique serait :
 
 
Constante
 
NbMaxNoeud = 200 /*  Dimension du tableau */
 
 
Type
 
Element = …. /* Etiquette de chaque noeud */
 
T_Pfils =  T_Fils /* Pointeur sur fils (liste) */
 
T_Pnoeud =  T_Nœud /* Pointeur sur Noeud (Tableau) */
 
 
T_Nœud = Enregistrement
 
Element Elt
 
T_Pfils Premierfils
 
Fin enregistrement T_Nœud
 
 
T_Arbre = NbMaxNoeud T_Noeud /* Vecteur */
 
 
T_Fils = Enregistrement
 
T_Pnoeud Noeudfils
 
T_Pfils FilsSuivant
 
Fin Enregistrement T_Fils
 
 
Variable
 
T_Arbre A
 
 
 
Et sa représentation graphique en utilisant l’arbre de la figure 11 serait :
 
 
N1 N2 N3 N4 N5 N6 N7 N8 N9 N10 N11 N12 N13 N14 N15 N16 Max
 
A
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figure 12. Représentation statique-Dynamique d’un arbre général
 
 
Remarque : Une possibilité est de transformer cette représentation en totale dynamique en remplaçant le tableau statique par une liste chaînée.
 
 
Représentation sous forme de N-uplet
 
 
SI l’on connaît le nombre maximum de fils que peut avoir un nœud, il y a possibilité de représenter l’arbre sous forme de n-uplet. Cette représentation est une extension de la représentation dynamique des arbres binaires. Là, le nombre de fils n’est pas deux, mais celui que l’on s’est fixé. Pour l’arbre de la figure 11, en supposant qu’il y ait cinq fils maximum, la description algorithmique serait la suivante :
 
 
Constante
 
NbMaxFils = 5 /*  Nombre maximum de fils */
 
Type
 
Element = …. /* Etiquette de chaque noeud */
 
T_PArbre =  T_Nœud /* Pointeur sur Noeud (n-uplet) */
 
T_Tabfils = NbMaxFils T_PArbre /* Tableau de pointeur sur fils */
 
T_Nœud = Enregistrement
 
Element Elt
 
T_Tabfils Fils
 
Fin enregistrement T_Nœud
 
Variable
 
T_PArbre A
 
 
Et sa représentation graphique en utilisant l’arbre de la figure 11 serait :
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figure 13. Représentation en n-uplet d’un arbre général
 
 
Remarque : La figure 13 ne correspond pas tout à fait à la déclaration précédente dans la mesure où elle ne représente que les pointeurs de chaque nœud et ne précise pas l’étiquette de ceux-ci.
 
 
Représentation sous forme d’arbre binaire
 
 
Le moyen de représenter les arbres généraux sous forme d’arbres binaires est d’utiliser le lien gauche comme premier fils et le lien droit comme frère droit. Cette représentation présente plusieurs avantages :
 
 
 Il y a un nœud par élément ni plus ni moins (bijection fils ainé-frère droit).
 
 Nous pouvons utiliser les algorithmes sur les arbres binaires (parcours, ajout de nœud, etc.) qui sont très simples à mettre en place.
 
 
Remarque : Nous utiliserons dans ce cas l’implémentation dynamique de l’arbre binaire.
 
 
La description algorithmique serait alors la suivante :
 
 
Type
 
Element = …. /* Définition du type des éléments */
 
T_Arbre =  T_Noeud /* type pointeur sur T_Noeud * /
 
T_Noeud  = Enregistrement
 
Element Elt
 
T_Arbre Premierfils,frèredroit
 
Fin Enregistrement T_Noeud
 
Variable
 
T_Arbre A
 
 
 
Ce qui pour l’arbre de la figure 11, la représentation graphique donnerait :
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figure 14. Représentation sous forme d’arbre binaire d’un arbre général
 
 
Travailler à l’aide de cet arbre est très simple. Par exemple pour connaître les fils d’un nœud, il suffit de parcourir le bord droit de son sous-arbre gauche.
 
 
Remarque : Nous pouvons noter que l’arbre obtenu n’est pas du tout équilibré.
 
 
Remarque 2 : Le parcours préfixe et le parcours symétrique de cet arbre binaire donne respectivement le même ordre que le parcours préfixe et le parcours postfixe de l’arbre général que celui-ci représente.
 
 
Parcours d’un arbre général
 
 
Pour parcourir un arbre général, on peut réaliser une extension du parcours en profondeur main gauche des arbres binaires. La différence réside dans le fait qu’il n’y a pas de traitement infixe, mais un traitement intermédiaire à chaque passage d’un fils à un autre. En d’autres termes, un nœud est rencontré son nombre de fils plus une fois : la descente sur le premier fils, les nombres de fils moins un passage intermédiaire d’un fils à l’autre et enfin, la remontée depuis le dernier fils (C’est pas clair Junior ?). L’algorithme employé pour ce parcours est celui du parcours d’arbre binaire « légèrement modifié ». En effet, il faut placer les traitements à l’intérieur d’une boucle dont le nombre d’itérations repose sur le nombre de fils que possède l’arbre parcouru.
 
Pour l’exemple, si l’on définit un arbre général A=< o, A1, A2, A3, A4, A5 >, nous obtiendrons graphiquement le parcours représenté en figure 15, soit :
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figure 15.Parcours profondeur main gauche d’un arbre général
 
 
Sur ce parcours, on peut constater que le nœud racine est visité six fois ; une fois en descendant vers A1 (traitement préfixe), quatre fois en passant de A1 à A2, A2 à A3, A3 à A4 et A4 à A5 (quatre traitements intermédiaires) et enfin en remontant de A5 (traitement suffixe).Et là Junior, tu crois qu’ils ont compris ?
 
 
L’algorithme abstrait du parcours en profondeur d’un arbre général est alors :
 
 
Algorithme procedure parcours
 
Paramètres locaux :
 
Arbre A
 
Variables
 
Entier i, nbfils
 
Debut
 
Nbfilsnb-arbres(liste-arbre(A))
 
Si feuille(A) alors
 
TERMINAISON /* traitement de terminaison */
 
Sinon
 
TRTpréfixe /* traitement 1 (préfixe) */
 
Pour i1 jusqu’à nbfils-1 Faire
 
parcours(ième(liste-arbre(A),i))
 
TRTintermédiaire /* traitement 2 (infixe) */
 
Fin pour
 
parcours(ième(liste-arbre(A),nbfils))
 
TRTsuffixe /* traitement 3 (postfixe) */
 
Fin si
 
Fin algorithme procedure parcours
 
 
Remarque : Nous utilisons une extension présentée lors du parcours d’arbre binaire à savoir : feuille. Cette opération devrait bien sûr être définie.
 
 
Remarque 2 : Le nombre de traitements possibles sur un nœud ne se limite pas à trois, mais peut être réellement égal au nombre de fils plus un. En effet, le traitement intermédiaire peut varier selon la valeur de l’indice de boucle et par conséquent renvoyer à un traitement particulier à chaque fois.
 
 
Par exemple, en utilisant l’arbre général de la figure 11, nous pourrions lister les nœuds de la manière suivante : (N1(N2(N7)(N8)(N9))(N3)(N4(N10)(N11))(N5)(N6(N12)(N13)(N14)(N15)(N16))), en utilisant l’algorithme ci-dessous :
 
 
Algorithme procedure parclisp
 
Paramètres locaux :
 
Arbre A
 
Variables
 
Entier i, nbfils
 
Debut
 
Nbfilsnb-arbres(liste-arbre(A))
 
Si feuille(A) alors
 
Ecrire(‘(‘,contenu(racine(A)),’)’) /* traitement de terminaison */
 
Sinon
 
Ecrire(‘(‘,contenu(racine(A))) /* traitement 1 (préfixe) */
 
Pour i1 jusqu’à nbfils-1 Faire
 
parcours(ième(liste-arbre(A),i))
 
Fin pour
 
parcours(ième(liste-arbre(A),nbfils))
 
Ecrire(‘)’) /* traitement 3 (postfixe) */
 
Fin si
 
Fin algorithme procedure parclisp
 
  
 
== Les algorithmes de recherche ==
 
== Les algorithmes de recherche ==

Version du 24 mars 2009 à 15:29

Sommaire

Les types abstraits

La conception d'un algorithme peut se faire de deux manières (une alternative, quoi !):

  • La première et aussi la plus simple est celle qui consiste à coder et à considérer uniquement les types de données créés pour l'occasion et correspondants au langage de programmation utilisé. Leur implémentation se fera via les déclarations de types du langage et l'on utilisera alors les méthodes (procédures et fonctions) qui leur sont propres. Il est alors parfois difficile de transcrire facilement l'algorithme vers un autre langage (du C vers le Caml par exemple ou réciproquement (je ne suis pas regardant!).
  • La deuxième méthode consiste à définir des types de données abstraits. C'est à dire que l'on va définir pour un type de donnée son nom, sa syntaxe d'utilisation (opérations, paramètres, etc.) et ses propriétés tout en étant détachés (algo lave plus blanc) de toutes les contingences propres à un langage de programmation et/ou à une machine. Si, par exemple, un problème nécessite l'utilisation d'un graphe, nous nous contenterons de penser à la résolution du problème sans nous soucier du comment sera implémenté ce graphe en mémoire, ni comment seront manipulées ses différentes composantes.

Les structures séquentielles

Nous présenterons dans ce chapitre les structures séquentielles "classiques", à savoir les listes, les piles et les files. Nous donnerons à chaque fois la définition du type abstrait correspondant accompagnée de quelques commentaires explicatifs. Puis nous fournirons les diverses implémentations de ces types ainsi que quelques algorithmes de manipulation. Les algorithmes seront fournis à chaque fois et dans la mesure du possible des deux manières: abstraite (en utilisant les opérations des types abstraits) et concrète (en utilisant le formalisme algorithmique vu en TD (voir en annexe le Mémo du langage algorithmique réalisé par Nathalie 'Junior' Bouquet).

les structures arborescentes

Un arbre est constitué d’éléments appelés noeuds organisés de façon hiérarchique. L’élément de base est la racine (Incroyable !). En informatique, comme dans la vraie vie, les arbres se rencontrent un peu partout : construction de répertoire, système d’exploitation, compilateur, etc.

Du à leur propriété structurelle récursive, les manipulations et les déclarations des arbres se font naturellement sous une forme récursive. Ce qui ne veut pas dire que la forme itérative ne leur soit pas applicable, mais elle est moins intuitive et souvent moins adaptée.

Les arbres se rencontrent à la base sous deux formes : les arbres binaires et les arbres généraux.

Les algorithmes de recherche

blablabla

blablabla

blablabla

blablabla

les tris simples

blablabla

blablabla

blablabla

blablabla



(Christophe "krisboul" Boullay)

Outils personnels
Cours d'algo EPITA :
Accès aux algorithmes :