البـــــوابـــة
Nous avons déjà vu la notion de fonction récursive dans le chapitre 2. Considérons à présent son équivalent dans les structures de données: la notion d'arbre. Un arbre est soit un arbre atomique (une feuille), soit un noeud et une suite de sous-arbres. Graphiquement, un arbre est représenté comme suit
noeud n1 est la racine de l'arbre, n5, n6, n7, n9, n10, n11 sont les feuilles, n1, n2, n3, n4, n8 les noeuds internes. Plus généralement, l'ensemble des noeuds est constitué des noeuds internes et des feuilles. Contrairement à la botanique, on dessine les arbres avec la racine en haut et les feuilles vers le bas en informatique. Il y a bien des définitions plus mathématiques des arbres, que nous éviterons ici. Si une branche relie un noeud ni à un noeud nj plus bas, on dira que ni est un ancêtre de nj. Une propriété fondamentale d'un arbre est qu'un noeud n'a qu'un seul père. Enfin, un noeud peut contenir une ou plusieurs valeurs, et on parlera alors d'arbres étiquetés et de la valeur (ou des valeurs) d'un noeud. Les arbres binaires sont des arbres tels que les noeuds ont au plus 2 fils. La hauteur, on dit aussi la profondeur d'un noeud est la longueur du chemin qui le joint à la racine, ainsi la racine est elle même de hauteur 0, ses fils de hauteur 1 et les autres noeuds de hauteur supérieure à 1.
Un exemple d'arbre très utilisé en informatique est la représentation des expressions arithmétiques et plus généralement des termes dans la programmation symbolique. Nous traiterons ce cas dans le chapitre sur l'analyse syntaxique, et nous nous restreindrons pour l'instant au cas des arbres de recherche ou des arbres de tri. Toutefois, pour montrer l'aspect fondamental de la structure d'arbre, on peut tout de suite voir que les expressions arithmétiques calculées dans la section 3.4 se représentent simplement par des arbres comme dans la figure 4.2 pour (* (+ 5 (* 2 3)) (+ (* 10 10) (* 9 9))). Cette représentation contient l'essence de la structure d'expression arithmétique et fait donc abstraction de toute notation préfixée ou postfixée.
Files de prioritéUn premier exemple de structure arborescente est la structure de tas (heap1 )utilisée pour représenter des files de priorité. Donnons d'abord une vision intuitive d'une file de priorité.
On suppose, comme au paragraphe 3.2, que des gens se présentent au guichet d'une banque avec un numéro écrit sur un bout de papier représentant leur degré de priorité. Plus ce nombre est élevé, plus ils sont importants et doivent passer rapidement. Bien sûr, il n'y a qu'un seul guichet ouvert, et l'employé(e) de la banque doit traiter rapidement tous ses clients pour que tout le monde garde le sourire. La file des personnes en attente s'appelle une file de priorité. L'employé de banque doit donc savoir faire rapidement les 3 opérations suivantes: trouver un maximum dans la file de priorité, retirer cet élément de la file, savoir ajouter un nouvel élément à la file. Plusieurs solutions sont envisageables.
La première consiste à mettre la file dans un tableau et à trier la file de priorité dans l'ordre croissant des priorités. Trouver un maximum et le retirer de la file est alors simple: il suffit de prendre l'élément de droite, et de déplacer vers la gauche la borne droite de la file. Mais l'insertion consiste à faire une passe du tri par insertion pour mettre le nouvel élément à sa place, ce qui peut prendre un temps O(n) où n est la longueur de la file.
Une autre méthode consiste à gérer la file comme une simple file du chapitre précédent, et à rechercher le maximum à chaque fois. L'insertion est rapide, mais la recherche du maximum peut prendre un temps O(n), de même que la suppression.
Une méthode élégante consiste à gérer une structure d'ordre partiel grâce à un arbre. La file de n éléments est représentée par un arbre binaire contenant en chaque noeud un élément de la file (comme illustré dans la figure 4.3). L'arbre vérifie deux propriétés importantes: d'une part la valeur de chaque noeud est supérieure ou égale à celle de ses fils, d'autre part l'arbre est quasi complet, propriété que nous allons décrire brièvement. Si l'on divise l'ensemble des noeuds en lignes suivant leur hauteur, on obtient en général dans un arbre binaire une ligne 0 composée simplement de la racine, puis une ligne 1 contenant au plus deux noeuds, et ainsi de suite (la ligne i contenant au plus 2i noeuds). Dans un arbre quasi complet les lignes, exceptée peut être la dernière, contiennent toutes un nombre maximal de noeuds (soit 2i). De plus les feuilles de la dernière ligne se trouvent toutes à gauche, ainsi tous les noeuds internes sont binaires, excepté le plus à droite de l'avant dernière ligne qui peut ne pas avoir de fils droit. Les feuilles sont toutes sur la dernière et éventuellement l'avant dernière ligne.
On peut numéroter cet arbre en largeur d'abord, c'est à dire dans l'ordre donné par les petits numéros figurant au dessus de la figure 4.3. Dans cette numérotation on vérifie que tout noeud i a son père en position ë i/2 û, le fils gauche du noeud i est 2i, le fils droit 2i + 1. Formellement, on peut dire qu'un tas est un tableau a contenant n entiers (ou des éléments d'un ensemble totalement ordonné) satisfaisant les conditions:
Ceci permet d'implémenter cet arbre dans un tableau a (voir figure 4.4) où le numéro de chaque noeud donne l'indice de l'élément du tableau contenant sa valeur
L'ajout d'un nouvel élément v à la file consiste à incrémenter n puis à poser a[n] = v. Ceci ne représente plus un tas car la relation a[n/2] ³ v n'est pas nécessairement satisfaite. Pour obtenir un tas, il faut échanger la valeur contenue au noeud n et celle contenue par son père, remonter au père et réitérer jusqu'à ce que la condition des tas soit vérifiée. Ceci se programme par une simple itération (cf. la figure 4.5).
static void ajouter (int v) {
++nTas;
int i = nTas - 1;
while (i > 0 && a [(i - 1)/2] <= v) {
a[i] = a[(i - 1)/2];
i = (i - 1)/2;
}
a[i] = v;
}
noeud n1 est la racine de l'arbre, n5, n6, n7, n9, n10, n11 sont les feuilles, n1, n2, n3, n4, n8 les noeuds internes. Plus généralement, l'ensemble des noeuds est constitué des noeuds internes et des feuilles. Contrairement à la botanique, on dessine les arbres avec la racine en haut et les feuilles vers le bas en informatique. Il y a bien des définitions plus mathématiques des arbres, que nous éviterons ici. Si une branche relie un noeud ni à un noeud nj plus bas, on dira que ni est un ancêtre de nj. Une propriété fondamentale d'un arbre est qu'un noeud n'a qu'un seul père. Enfin, un noeud peut contenir une ou plusieurs valeurs, et on parlera alors d'arbres étiquetés et de la valeur (ou des valeurs) d'un noeud. Les arbres binaires sont des arbres tels que les noeuds ont au plus 2 fils. La hauteur, on dit aussi la profondeur d'un noeud est la longueur du chemin qui le joint à la racine, ainsi la racine est elle même de hauteur 0, ses fils de hauteur 1 et les autres noeuds de hauteur supérieure à 1.
Un exemple d'arbre très utilisé en informatique est la représentation des expressions arithmétiques et plus généralement des termes dans la programmation symbolique. Nous traiterons ce cas dans le chapitre sur l'analyse syntaxique, et nous nous restreindrons pour l'instant au cas des arbres de recherche ou des arbres de tri. Toutefois, pour montrer l'aspect fondamental de la structure d'arbre, on peut tout de suite voir que les expressions arithmétiques calculées dans la section 3.4 se représentent simplement par des arbres comme dans la figure 4.2 pour (* (+ 5 (* 2 3)) (+ (* 10 10) (* 9 9))). Cette représentation contient l'essence de la structure d'expression arithmétique et fait donc abstraction de toute notation préfixée ou postfixée.
Files de prioritéUn premier exemple de structure arborescente est la structure de tas (heap1 )utilisée pour représenter des files de priorité. Donnons d'abord une vision intuitive d'une file de priorité.
On suppose, comme au paragraphe 3.2, que des gens se présentent au guichet d'une banque avec un numéro écrit sur un bout de papier représentant leur degré de priorité. Plus ce nombre est élevé, plus ils sont importants et doivent passer rapidement. Bien sûr, il n'y a qu'un seul guichet ouvert, et l'employé(e) de la banque doit traiter rapidement tous ses clients pour que tout le monde garde le sourire. La file des personnes en attente s'appelle une file de priorité. L'employé de banque doit donc savoir faire rapidement les 3 opérations suivantes: trouver un maximum dans la file de priorité, retirer cet élément de la file, savoir ajouter un nouvel élément à la file. Plusieurs solutions sont envisageables.
La première consiste à mettre la file dans un tableau et à trier la file de priorité dans l'ordre croissant des priorités. Trouver un maximum et le retirer de la file est alors simple: il suffit de prendre l'élément de droite, et de déplacer vers la gauche la borne droite de la file. Mais l'insertion consiste à faire une passe du tri par insertion pour mettre le nouvel élément à sa place, ce qui peut prendre un temps O(n) où n est la longueur de la file.
Une autre méthode consiste à gérer la file comme une simple file du chapitre précédent, et à rechercher le maximum à chaque fois. L'insertion est rapide, mais la recherche du maximum peut prendre un temps O(n), de même que la suppression.
Une méthode élégante consiste à gérer une structure d'ordre partiel grâce à un arbre. La file de n éléments est représentée par un arbre binaire contenant en chaque noeud un élément de la file (comme illustré dans la figure 4.3). L'arbre vérifie deux propriétés importantes: d'une part la valeur de chaque noeud est supérieure ou égale à celle de ses fils, d'autre part l'arbre est quasi complet, propriété que nous allons décrire brièvement. Si l'on divise l'ensemble des noeuds en lignes suivant leur hauteur, on obtient en général dans un arbre binaire une ligne 0 composée simplement de la racine, puis une ligne 1 contenant au plus deux noeuds, et ainsi de suite (la ligne i contenant au plus 2i noeuds). Dans un arbre quasi complet les lignes, exceptée peut être la dernière, contiennent toutes un nombre maximal de noeuds (soit 2i). De plus les feuilles de la dernière ligne se trouvent toutes à gauche, ainsi tous les noeuds internes sont binaires, excepté le plus à droite de l'avant dernière ligne qui peut ne pas avoir de fils droit. Les feuilles sont toutes sur la dernière et éventuellement l'avant dernière ligne.
On peut numéroter cet arbre en largeur d'abord, c'est à dire dans l'ordre donné par les petits numéros figurant au dessus de la figure 4.3. Dans cette numérotation on vérifie que tout noeud i a son père en position ë i/2 û, le fils gauche du noeud i est 2i, le fils droit 2i + 1. Formellement, on peut dire qu'un tas est un tableau a contenant n entiers (ou des éléments d'un ensemble totalement ordonné) satisfaisant les conditions:
| <table cellSpacing=2 cellPadding=0><tr><td noWrap align=right>2 £ 2i £ n </TD> <td noWrap align=middle>Þ</TD> <td noWrap align=left> a[2i] ³ a[i]</TD></TR> <tr><td noWrap align=right>3£ 2i+1 £ n </TD> <td noWrap align=middle>Þ</TD> <td noWrap align=left> a[2i+1] ³ a[i] </TD></TR></TABLE> |
Ceci permet d'implémenter cet arbre dans un tableau a (voir figure 4.4) où le numéro de chaque noeud donne l'indice de l'élément du tableau contenant sa valeur
L'ajout d'un nouvel élément v à la file consiste à incrémenter n puis à poser a[n] = v. Ceci ne représente plus un tas car la relation a[n/2] ³ v n'est pas nécessairement satisfaite. Pour obtenir un tas, il faut échanger la valeur contenue au noeud n et celle contenue par son père, remonter au père et réitérer jusqu'à ce que la condition des tas soit vérifiée. Ceci se programme par une simple itération (cf. la figure 4.5).
static void ajouter (int v) {
++nTas;
int i = nTas - 1;
while (i > 0 && a [(i - 1)/2] <= v) {
a[i] = a[(i - 1)/2];
i = (i - 1)/2;
}
a[i] = v;
}
