Structures arborescentes

La notion de type abstrait de donnée

Denis Lapoire

Ce cours présentera dans un premier temps la notion de type abstrait de donnée. Nous verrons certains types abstraits (ensemble, tableau, liste, file, pile) ainsi que différentes implémentations de ceux-ci.

Commentez

- Titre : Structures arborescentes

- Auteur : Denis Lapoire

- Parution : 22 novembre 2006

- Licence : Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2017 Denis Lapoire. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- 1. Chapitre 1 - Introduction

- 1-1. De l'abstrait au concret et inversement

- 1-2. Brefs rappels mathématiques

- 1-2-1. Ensemble

- 1-2-2. Relation binaire

- 1-2-3. Fonction

- 1-2-4. Séquence

- 1-3. Un type abstrait : l'ensemble

- 1-3-1. À taille constante

- 1-3-2. À taille proportionnelle à la cardinalité de l'ensemble représenté

- 1-3-3. Représentations par une « séquence »

- 1-3-4. Représentation par un arbre

- 2. Chapitre 2 - Types abstraits

- 2-1. Un exemple de type abstrait : le type ensemble

- 2-1-1. Quelles opérations choisir ?

- 2-1-2. Quels axiomes choisir ?

- 2-1-3. Écriture formelle des axiomes

- 2-2. Quelques types abstraits « séquence »

- 2-2-1. Le tableau

- 2-2-2. La structure

- 2-2-3. La pile

- 2-2-4. La file

- 2-2-5. La liste

- 2-3. Conclusion

- 3. Chapitre 3 - Implémentations de types

- 3-1. Types primitifs et effets de bord

- 3-1-1. Types primitifs

- 3-1-2. Effets de bord

- 3-2. Tableau infini

- 3-3. Représentation d'une pile par une zone mémoire contiguë

- 3-4. Représentation d'une liste itérative à l'aide d'un chaînage

- 3-4-1. Encapsulation du type élément dans un nœud

- 3-4-2. Sentinelle avant

- 3-4-3. Autre attribut de la liste : sa longueur

- 3-4-4. Un autre attribut de la liste : le curseur

- 3-4-5. Implémentation du type liste

- 3-4-6. Implémentation d'un nouveau type liste

- 3-5. Conclusion

- 4. Chapitre 4 - Arbres binaires

- 4-1. Définition

- 4-2. Arbre binaire parfait

- 4-3. Implémentation chaînée d'un arbre binaire

- 4-3-1. Définitions des primitives

- 5. Chapitre 5 - Parcours d'arbres

- 5-1. Parcours en profondeur

- 5-1-1. Parcours préfixe, infixe ou suffixe

- 5-1-2. Écriture itérative d'un parcours en profondeur

- 5-2. Parcours en largeur

- 6. Chapitre 6 - Arbres binaires de recherche

- 6-1. Définitions

- 6-2. Le problème Recherche

- 6-3. Insertion d'un nouveau nœud

- 6-4. Le problème du successeur

- 6-5. Suppression d'un nœud dans un arbre binaire

- 6-6. Conclusion

- 7. Chapitre 7 - Les arbres rouges et noirs

- 7-1. Définition

- 7-2. Une opération locale : la rotation

- 7-3. Insérer un nœud

- 7-3-1. Correction sommaire

- 7-3-2. Complexité

- 7-4. Suppression

- 7-4-1. Correction très sommaire

- 7-4-2. Complexité

- 8. Chapitre 8 - Le type partition

- 8-1. Préalables mathématiques

- 8-2. Un type abstrait partition

- 8-3. Quelques premières implémentations

- 8-3-1. À l'aide de séquences et de listes chaînées

- 8-3-2. À l'aide d'étoiles (arbres de hauteur 1)

- 8-4. Implémentation à l'aide d'arbres

- 8-4-1. Une première implémentation

- 8-4-2. Une seconde implémentation

- 8-4-3. Calcul des complexités

- 8-5. Utilisation de partition

- 9. Remerciements

1 - Chapitre 1 - Introduction

Le cours précédent d'Initiation Algorithmique a présenté les deux notions de problèmes et d'algorithme. Il a insisté sur différentes familles d'algorithmes (algorithme glouton, algorithme divide and conquer, programmation dynamique). Il a montré comment un même problème pouvait être résolu par des algorithmes différents appartenant à ces différentes familles. La qualité première attendue de ces algorithmes était leur correction.

Nous nous intéresserons ici plus particulièrement à une seconde qualité à savoir leur moindre coût en termes d'utilisation d'espace mémoire et de temps.

À cette fin, nous verrons comment représenter un ensemble dans une zone mémoire de la machine sur laquelle est exécuté un programme, et ce en définissant un objet intermédiaire : le type abstrait.

1-1 - De l'abstrait au concret et inversement

Les problèmes algorithmiques rencontrés lors de ce semestre admettent pour entrée principalement un unique objet plus complexe que de simples éléments : l'objet ensemble.

Le modèle de calcul, c'est-à-dire la représentation conceptuelle de la machine sur laquelle sont exécutés les programmes, fournit une mémoire dont les accès en lecture et en écriture se font en temps constant pourvu que l'on ait l'adresse des octets à lire ou modifier. Ainsi, d'un point de vue théorique, la zone mémoire peut être considérée comme un immense tableau.

Les algorithmes que nous souhaitons écrire sont des algorithmes possédant la plupart des propriétés ci-dessous :

- leur indépendance vis-à-vis et de la machine et du langage de programmation dans lequel sera écrit le programme ;

- la simplicité d'écriture, qui permet leur compréhension et la preuve de leur correction ;

- leur faible complexité en temps et en espace.

En conséquence, les algorithmes ne seront pas écrits en code assembleur, mais dans un langage de haut niveau. Ainsi, dans un algorithme ne seront pas décrites les instructions de bas niveau accédant à telle ou telle adresse de la zone mémoire. Cette tâche est dévolue à des fonctions auxiliaires utilisées dans l'algorithme qui seront regroupées dans des ensembles logiques cohérents que nous nommons « types abstraits ».

Ainsi, entre l'objet mathématique très abstrait qu'est l'ensemble et l'objet très concret le tableau qui est la zone mémoire, nous concevrons et manipulerons :

1. De nouveaux objets mathématiques plus structurés que l'ensemble, par exemple la séquence, la relation ;

2. Des types abstraits qui réalisent cette interface entre un univers mathématique logique et un univers informatique calculatoire. Ainsi, chaque type abstrait sera un ensemble d'opérations défini logiquement et pouvant être implémenté à l'aide de programmes exécutables. Ces types abstraits auront pour nom l'ensemble, le tableau, la structure, la pile, la file, la liste, l'arbre binaire, le tas, etc.

1-2 - Brefs rappels mathématiques

La connaissance et la maîtrise des notions suivantes sont indispensables. Se référer à tout ouvrage de mathématiques.

1-2-1 - Ensemble

Un ensemble est un objet mathématique qui possède d'autres objets appelés ses éléments ; l'appartenance de l'élément à l'ensemble est noté .

L'ensemble vide, noté , est l'unique ensemble ne contenant aucun élément.

Un singleton est un ensemble contenant un unique élément. Une paire est un ensemble contenant exactement deux éléments.

Notions et notations importantes

Intervalle, cardinalité, partie, opération union, intersection, différence, complément.

1-2-2 - Relation binaire

Le produit cartésien de deux ensembles et est l'ensemble noté ayant pour éléments tous les couples de la forme avec et .

Une relation binaire définie sur et est une partie du produit cartésien . L'appartenance est souvent notée .

Notions et notations importantes

Réflexivité, associativité, symétrie, relation d'ordre (partiel ou total), relation bien fondé, relation d'équivalence, classes d'équivalence, les ensembles et , intervalle d'entiers, relation d'arité .

1-2-3 - Fonction

Étant donnés deux ensembles et , une fonction de vers est une relation binaire telle que pour tout élément il existe un et un seul élément tel que . L'appartenance est notée .

Notions et notations importantes

Injectivité, surjectivité, bijectivité, morphisme, isomorphisme, composition, restriction, inverse, involution, permutation.

1-2-4 - Séquence

Une séquence à valeurs dans un ensemble est une fonction de la forme ou de la forme avec . Dans ce dernier cas, la séquence peut être notée , l'entier éventuellement nul, est la longueur de .

La séquence vide définie à partir de est notée et est de longueur 0.

Notions et notations importantes

Sous-séquence extraite, concaténation, mot.

1-3 - Un type abstrait : l'ensemble

Le type abstrait qui sera le fil conducteur de ce cours est le type ensemble. Sa signature est simplement :

estVide

: ensemble

→ booléen

ensembleVide

:

→ ensemble

appartient

: élément x ensemble

→ booléen

ajouter

: élément x ensemble

→ ensemble

enlever

: élément x ensemble

→ ensemble

choisir

: ensemble

→ élément

En supposant que l'on mette à votre disposition chacun des types cités, comment implémenter de façon optimale à l'aide de l'un de ces types ce type ensemble. Il n y a pas de réponse à une telle question. Tout dépend :

1. D'informations supplémentaires sur la réalité des ensembles manipulés. Quelle est leur cardinalité ? Quelle est la cardinalité de leur univers ? Quelles sont les relations et opérations opérant sur les éléments de ces ensembles ?

2. D'informations sur les opérations les manipulant ? Quelles sont les primitives jamais ou rarement utilisées ? souvent utilisées ?

3. Et plus généralement de l'algorithme considéré.

Afin de faciliter l'écriture algorithmique, nous séparons :

1. L'écriture d'un algorithme utilisant par exemple le type ensemble ;

2. De l'implémentation du type ensemble et la compréhension de l'exécution machine de ses primitives.

Cette séparation est nécessaire dans une première étape et permet en distinguant les deux problèmes de pouvoir les résoudre plus facilement, car séparément. Dans la dernière étape conclusive, le choix de l'implémentation devra être justifié en considérant à la fois l'algorithme et l'implémentation et ainsi permettre d'évaluer le choix de cet algorithme et de cette implémentation en tentant de répondre à la question :

- est-ce que pour cet algorithme, cette implémentation permet d'avoir une complexité en temps (et ou en espace) optimale ?

- Est-ce que pour le problème considéré, cet algorithme et ce cette implémentation ont une une complexité en temps (et ou en espace) optimale ?

Deux familles d'implémentations

Cette section balaie très rapidement les liens entre différentes stratégies de représentation machine d'un ensemble et leurs liens avec les notions de séquence ou d'arbre.

L'implémentation d'un type abstrait sera réalisée à l'aide d'autres types abstraits. Cependant l'analyse des coûts en temps et en espace nécessite de comprendre la façon dont l'objet sera représenté in fine sur la machine. Rappelons que la mémoire est formée d'un nombre N de blocs de même taille, identifiés par des adresses ; l'accès au contenu de chacun de ces blocs à partir de son adresse se faisant en temps constant.

1-3-1 - À taille constante

Une première classe d'implémentations machine sont celles qui utilisent un nombre de blocs constant pour mémoriser un ensemble de taille variable (pourvu qu'il ne dépasse pas une certaine cardinalité).

Tableaux de booléens

Une façon de représenter l'ensemble du dernier tirage au Loto {3, 7, 13, 19, 23, 25, 28} est d'utiliser le tableau de booléens à indices 1, […] , 49 suivant :

indices: 01 02 03 04 05 06 O07 08 09 10 11 12 13 14 15 16 17 18 19 20
valeurs:  0  0  1  0  0  0  1  0  0  0  0  0  1  0  0  0  0  0  1   0

indices: 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
valeurs:  0  0  1  0  1  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0

indices: 41 42 43 44 45 46 47 48 49
valeurs:  0  0  0  0  0  0  0  0  0

L'avantage d'une telle représentation est de pouvoir exécuter les différentes primitives appartient, enlever, ajouter en temps constant. Constante qui dépend de l'accès à un bloc mémoire ; l'opération dure une fraction de seconde.

Les exécutions de estVide, ensVide, choisir sont ici aussi en temps constant ; mais une constante éventuellement importante, proportionnelle au nombre d'indices. En ajoutant un nouveau champ indiquant le nombre d'éléments de l'ensemble, nous obtenons une complexité en temps de estVide « petitement » constant.

Dans l'exemple ci-dessus, la solution est envisageable, car l'univers de tous les éléments possibles d'un ensemble est de cardinalité « proche » (49 dans l'exemple) de celle de l'ensemble (7 dans l'exemple).

Tables de hachage

Supposons que l'on s'intéresse à l'ensemble des patronymes français (que nous supposerons au nombre de 100 000 = 10^5 tirages).

Sachant qu'un caractère latin est codé à l'aide de 5 bits et qu'un patronyme possède au plus 20 caractères, on pourrait utiliser un tableau de booléens à ensemble d'indices 25…20 ≃ 10^30. Le coût et la perte de mémoire sont alors prohibitifs (seul 10-23 % de l'espace est réellement utilisé !).

Une idée consiste à transformer selon une fonction de hachage chacun des noms en une valeur de taille inférieure par exemple ayant 6 digits (le nombre d'indices du tableau est ainsi ramené de 10^3^0 à 10^6.

L'ensemble {PICCOLET D'HERMILLON, PICHAT,...} est ainsi représenté par le tableau

indices : ... h(PICCOLET D'HERMILLON) ... h(PICHAT)
valeurs : ...  PICCOLET D'HERMILLON   ... PICHAT

Observons qu'avec une telle représentation, toutes les « bonnes » propriétés du tableau à valeurs booléennes sont conservées. Les opérations sont à coût constant.

Une première difficulté apparaît : l'existence de collisions à savoir des tirages ayant même hachés ().

1-3-2 - À taille proportionnelle à la cardinalité de l'ensemble représenté

Différents choix s'offrent alors.

1-3-3 - Représentations par une « séquence »

Une façon naturelle de représenter tout ensemble par une séquence : c'est-à-dire par exemple, représenter l'ensemble {3, 7, 13, 19, 23, 25,28} par la séquence (13, 23, 3, 7, 28, 25, 19). Observons ici les différents choix qui s'offrent selon que :

1. On autorise ou non la duplication des éléments. A-t-on intérêt à représenter {3, 7, 13, 19, 23, 25, 28} par la séquence (3, 7, 13, 19, 13, 19, 28, 3, 3, 23, 25, 28) ?

2. On impose ou non que les éléments apparaissent dans la séquence en respectant l'éventuel ordre total de l'ensemble. A-t-on intérêt à représenter {3, 7, 13, 19, 23, 25, 28} par la séquence (3, 7, 13, 19, 23, 25, 28) ?

Les types abstraits permettant d'implémenter de telles séquences ne manquent pas :

1. Le type Tableau ;

2. Le type Pile ;

3. Le type File ;

4. Le type Liste.

Représentation contiguë

Une première technique pour représenter la liste (3, 7, 13, 19, 23, 25, 28) est d'utiliser 7 blocs mémoire contigus dont les adresses définissent intrinsèquement l'ordre des éléments qu'elles contiennent.

La liste (3, 7, 13, 19, 23, 25, 28) peut ainsi avoir pour représentation machine :

adresses 12123 12124 12125 12126 12127 12128 12129
contenus     3     7    13    19    23    25    28

Cette représentation est la représentation naturelle du type Tableau ; cette proximité entre ce type et cette implémentation ne doit cependant pas être considérée comme absolue : en conclusion de ce chapitre, nous verrons pourquoi représenter des tableaux sous la forme de listes chaînées !

L'un des inconvénients d'une telle représentation est la gestion de cet espace mémoire. Si au cours de l'exécution de votre algorithme, vous souhaitiez augmenter l'ensemble {3, 7, 13, 19, 23, 25, 28} d'un seul élément et si les blocs se trouvant aux adresses 12122 et 12130 n'étaient pas libres, il serait alors nécessaire de trouver un minimum de 8 blocs contigus libres et de recopier tous les éléments.

Représentation par chaînage

Une technique pour implémenter l'un de ces types est le chaînage c'est-à-dire d'accoler à l'élément de la séquence l'adresse de l'élément qui lui succède. Ainsi la séquence (13, 23, 3, 7, 28, 25, 19) aura par exemple pour représentation-machine l'ensemble des blocs d'adresses respectives :

adresses    12123   12231    13213    34548    90808    98773     98799

ayant respectivement pour contenu :

contenus 28:90808 7:12123 23:98799 13:13213 25:98773 19 :------ 3:12231

L'avantage d'une telle méthode est de pouvoir en temps contant :

1. Supprimer un élément de la séquence, pourvu que l'on ait son adresse ;

2. Ajouter un élément qui n'est pas déjà présent dans la séquence ;

3. Tester si une séquence est vide ;

4. Créer une liste vide.

L'un des inconvénients est de se mettre en situation de parcourir jusqu'à la séquence tout entière pour :

1. Pour décider si un élément s'y trouve ;

2. Calculer l'adresse d'un élément de cette séquence.

1-3-4 - Représentation par un arbre

Décider en temps linéaire l'appartenance d'un élément à un ensemble étant un handicap, une alternative convaincante à la structure unidimensionnelle qu'est la séquence, c'est l'arbre, un objet bidimensionnel.

Différentes sortes d'arbres existent. Ceux étudiés dans ce cours seront tous « enracinés », c'est-à-dire possédant un sommet singulier appelé la « racine » de l'arbre. Citons-en quelques-uns :

- les arbres binaires de recherche ;

- les arbres rouges et noirs, une variante des précédents ;

- les tas.

L'idée commune à ces arbres est d'utiliser les propriétés relatives des éléments (en supposant qu'ils sont munis d'un ordre total : ce qui peut toujours être supposé) pour les placer intelligemment dans une structure dans laquelle la recherche d'un élément ne nécessite pas de parcourir tous les éléments comme cela se passe dans une séquence chaînée.

Arbre binaire

L'exemple le plus simple est l'arbre binaire de recherche dans lequel tout nœud de l'arbre possède (généralement) un nœud fils gauche et un nœud fils droit et tels que les trois éléments de ces trois nœuds , , vérifient respectivement .

L'ensemble {3, 7, 13, 19, 23,25, 28} peut ainsi être représenté par l'arbre suivant :

FIG. 1.1 - Un arbre binaire de recherche

L'ensemble des opérations

appartient

ensemble, ensemble

→ booléen

ajouter

élément, ensemble

→ ensemble

enlever

élément, ensemble

→ ensemble

admettent des algorithmes de complexité en temps proportionnel à la hauteur de l'arbre. Ces algorithmes seront étudiés dans le chapitre 6.

Des techniques relativement simples peuvent garantir qu'une hauteur d'arbre raisonnable, voire optimale, à savoir où est la cardinalité de l'ensemble. L'une de ces techniques est justement le fait des arbres rouges et noirs.

Tas : un exemple remarquable de limiter les primitives au strict minimum

Parfois le type ensemble utilisé est dégradé, c'est-à-dire défini à partir du type ensemble présenté plus haut en :

- supprimant une ou plusieurs opérations ;

- en restreignant l'utilisation d'une ou plusieurs opérations.

Par exemple, l'opération enlever peut consister uniquement à supprimer l'élément de plus grande valeur. Cet appauvrissement du type ensemble facilite fortement son implémentation. Une solution souvent retenue est l'utilisation d'arbres binaires appelés « tas » dans lequel l'élément d'un nœud est supérieur aux éléments des fils. Ainsi, l'élément minimal se trouve à la racine. Calculer l'élément maximal de l'ensemble consiste alors simplement à considérer l'élément se trouvant à la racine de l'arbre! Nous verrons comment supprimer cet élément ou ajouter tout nouvel élément en temps logarithmique.

Forêts

D'autres variantes du type ensemble existent. Par exemple une qui permet de manipuler une partition d'un ensemble donné en n'autorisant que les unions de ces parties. Les arbres sont une nouvelle fois utilisés et permettent (pour certains algorithmes) de réaliser l'union de deux parties à partir de deux de leurs éléments en temps (quasi) constant !

2 - Chapitre 2 - Types abstraits

Intuitivement un type abstrait est un ensemble d'opérations pour lesquelles on définit une syntaxe et une sémantique. Plus formellement un type abstrait est la donnée :

- de sa signature décrivant la syntaxe du type, les noms des types utilisés pour sa définition) ainsi que le nom des opérations et le type de leurs arguments ;

- d'un ensemble d'axiomes définissant les propriétés des opérations.

La définition d'un tel ensemble d'axiomes est un exercice parfois délicat, car cet ensemble doit être à la fois :

- consistant c'est-à-dire les axiomes ne doivent pas être contradictoires ;

- complet, c'est-à-dire les axiomes sont suffisants pour décrire l'ensemble des propriétés du type abstrait.

Exemple 1

Ainsi, le type primitif booléen peut ainsi être défini :

Nom Booléen

Opérations

vrai

: booléen

→ booléen

faux

: booléen

→ booléen

¬

: booléen

→ booléen

∧

: booléen x booléen

→ booléen

∨

: booléen x booléen

→ booléen

Les axiomes sont :

5. etc.

Lors de la définition d'un type abstrait, il est recommandé pour des raisons de simplicité de limiter le nombre d'opérations. Dans le cas présent, on démontre aisément que toute opération booléenne peut s'écrire sous forme normale disjonctive, c'est-à-dire sous la forme d'une disjonction (opérateur « OU ») de conjonctions (opérateur « ET » ) de littéraux positifs (variable simple) ou négatifs (variable précédée de l'opérateur ). Par exemple, l'opération se définit par  ; l'opération se définit par .

Remarque 1 Le plus célèbre des théorèmes en informatique est le théorème dit d'incomplétude de Godel qui indique qu'aucun ensemble fini d'axiomes n'est suffisant pour prouver l'ensemble des propriétés du type entier. Ainsi, formellement il est impossible de définir un type abstrait entier qui soit universel. Cependant, rassurez-vous. Le type entier ou tout autre type que vous serez amené à définir doit l'être dans le contexte de quelques algorithmes à écrire, dont la correction ou la terminaison nécessitent un nombre fini de propriétés sur ces entiers, et donc, d'un nombre fini d'axiomes.

2-1 - Un exemple de type abstrait : le type ensemble

Définir un type abstrait est réalisé en fonction du contexte, c'est-à-dire en fonction du problème à résoudre, voire de l'algorithme le résolvant. Définir un type abstrait consiste à choisir un ensemble d'opérations. Réaliser un tel choix nécessite un arbitrage entre différents critères :

1. Faire des choix conformes avec des définitions courantes ;

2. Simplicité de la définition du type : que ce soit en ce qui concerne le nombre d'opérations, ou la définition des axiomes ;

3. Simplicité de la définition de l'algorithme ;

4. Optimisation de l'algorithme en ce qui concerne sa complexité en temps ou en espace.

2-1-1 - Quelles opérations choisir ?

Considérons le type ensemble. Pour des raisons de simplicité, l'ensemble de ces opérations doit être minimal tout en étant suffisant pour permettre l'écriture de l'algorithme. Une définition universelle semblerait être :

Nom ensemble

Utilise élément , booléen

Opérations

estVide

: ensemble

→ booléen

ensembleVide

:

→ ensemble

appartient

: élément x ensemble

→ booléen

ajouter

: élément x ensemble

→ ensemble

enlever

: élément x ensemble

→ ensemble

choisir

: ensemble

→ élément

Considérons un algorithme qui nécessite de calculer régulièrement la cardinalité d'un ensemble. Cette opération peut être définie à l'aide des opérations précédentes :

1. fonction cardinalité(E:ensemble) :entier

2. i ← 0;

3. tantque ¬(estVide(E))

4. i ← i + 1;

5. E ← enlever(choisir(E),E);

6. retourner i;

Cependant, la complexité en temps de l'exécution de cette fonction (ici linéaire) peut s'avérer excessive alors que cette opération peut s'exécuter en temps constant par la simple présence dans la structure implémentant le type ensemble d'un entier indiquant sa cardinalité. Aussi, dans le cas où l'algorithme considéré requiert de calculer souvent la taille de l'ensemble ou, plus encore, si sa complexité en temps dépend de l'exécution de cardinalité en temps constant, il est préférable d'ajouter l'opération cardinalité : ensemble → entier dans la définition même du type.

2-1-2 - Quels axiomes choisir ?

Que signifient les opérations suivantes ?

ajouter

élément x ensemble

→ ensemble

enlever

élément x ensemble

→ ensemble

Quatre significations s'offrent à nous selon que l'on accepte ou non l'exécution de l'opération ajouter sur un élément contenu dans l'ensemble et selon que l'on accepte ou non l'exécution de l'opération enlever sur un élément n'appartenant pas à l'ensemble.

Exemple 2 Supposons que nous souhaitions écrire un algorithme réalisant l'union de deux ensembles. Si l'opération ajouter peut s'exécuter sur un élément déjà présent dans l'ensemble, l'algorithme s'écrit simplement :

1. fonction union1(A,B:ensemble) :ensemble

2. tantque ¬(estVide (B))

3. b ← choisir(B);

4. B ← enlever(b,B);

5. A ← ajouter(b,A);

6. retourner A;

Si l'opération ajouter ne peut pas s'exécuter sur un élément déjà présent dans l'ensemble, l'algorithme s'écrit simplement :

1. fonction union2(A,B:ensemble) :ensemble

2. tantque ¬(estVide(B))

3. b ← choisir(B);

4. B ← enlever(b,B);

5. si ¬(appartient(a,A)) alors

6. A ← ajouter(b,A);

7. retourner A;

Si l'on considère les deux critères que sont la simplicité de l'algorithme et sa complexité en temps, la préférence va à la première solution : le code est plus simple, la complexité en temps est au moins aussi bonne que la seconde.

Exemple 3 Supposons que l'on souhaite ne retenir d'un ensemble que les entiers pairs. Une solution à ce problème est :

1. fonction impairs(A :ensemble) :ensemble

2. B ← ensVide();

3. tantque ¬(estVide(A)

4. a ← choisir(A);

5. A ← enlever(a,A);

6. si estPair(a) alors

7. B ← ajouter(a,B);

8. retourner B;

Ici, nous savons que tout élément candidat à être ajouté dans l'ensemble ne peut pas y appartenir. Nous avons donc tout intérêt à définir l'opération ajouter en interdisant l'ajout d'un élément déjà présent, et ce pour au moins deux raisons :

1. En restreignant la puissance opératoire de ajouter, son implémentation peut être moins coûteuse en temps. Si l'ensemble est représenté par une liste sans répétition, l'ajout d'un élément non présent est fait en temps constant : on l'insère en première position. Par contre, l'ajout d'un élément éventuellement déjà présent nécessite de vérifier sa présence avant de l'y insérer ;

2. En restreignant la puissance opératoire de ajouter, on détecte d'éventuelles erreurs dans l'écriture d'un exécutable. Vous pourrez demander lors de l'exécution de votre programme de vous signaler toute tentative d'ajouter un élément déjà présent et utiliser ce signal pour détecter une erreur soit dans le programme soit dans l'algorithme lui-même.

2-1-3 - Écriture formelle des axiomes

Définir le sens des opérations est réalisé à l'aide d'axiomes, c'est-à-dire de formules logiques. Contrairement à une définition mathématique où l'on restreint la portée d'une fonction en restreignant les domaines des arguments, lors d'une définition axiomatique on restreint la portée d'une fonction en ne définissant le sens que pour des valeurs appartenant à des domaines précis.

Exemple 4 Considérons l'opération enlever que l'on autorise à opérer sur un élément h n'appartenant pas éventuellement à un ensemble .

L'opération ensembliste mathématique sous-jacente est la fonction qui à tout ensemble et à tout élément associe l'ensemble à .

Sa définition axiomatique est :

Exemple 5 Considérons l'opération ajouter que l'on autorise à opérer sur un élément appartenant nécessairement à un ensemble .

L'opération ensembliste mathématique sous-jacente est la fonction qui à tout ensemble et à tout élément associe l'ensemble noté égal à .

Le mathématicien considèrera que l'expression est incorrecte.

La définition axiomatique de enlever est :

L'axiomatique garantit des propriétés dans la mesure ou les spécifications des fonctions ont été respectées : ici, on ne peut ajouter un élément à un ensemble qu'à la condition qu'il n'y appartienne pas. Si cette condition n'est pas respectée, l'algorithme peut s'exécuter, mais sa correction n'est pas garantie.

Par exemple, l'informaticien admettra éventuellement que l'algorithme suivant puisse s'exécuter :

1. fonction test(): booléen

2. A ← ensembleVide();

3. A ← ajouter(1,A);

4. A ← ajouter(1,A);

5. A ← enlever(1,A);

6. retourner appartient(1,A);

Cependant, il ne garantira pas que le booléen évaluant l'expression appartient(1, A) soit faux !

Ceci n'est pas une coquetterie obscure. Démontrons qu'une implémentation correcte, naturelle et efficace du type ensemble a pour conséquence que test() retourne vrai.

Implémentons le type ensemble à l'aide d'une liste d'éléments sans répétition, et ce, sans se soucier de l'ordre des éléments. Une implémentation efficace de ajouter(a, A) est d'insérer a au premier rang de la liste (représentant) A. Une implémentation efficace de enlever(1, A) est de supprimer la première occurrence de 1 dans la liste A : puisqu'aucune répétition n'est admise dans la liste, il n'est pas utile de supprimer toutes les occurrences de 1, mais seulement la première.

Ainsi, lors de l'exécution de test l'ensemble A est successivement représenté par :

1. ()

2. (1)

3. (1,1)

4. (1)

Le booléen retourné par l'appel de test() est ainsi vrai.

2-2 - Quelques types abstraits « séquence »

Il existe plusieurs façons de manipuler une séquence. Nous en présenterons cinq principales qui forment autant de types abstraits :

- le tableau ;

- la structure ;

- la pile ;

- la file ;

- la liste.

Cette liste n'est pas exhaustive. Vous serez parfois amené à en définir de nouvelles inspirées ou non de celles-ci. De même, vous serez parfois amené à enrichir l'une d'entre elles en ajoutant de nouvelles primitives.

2-2-1 - Le tableau

Le premier type abstrait est le type tableau. Les opérations « tableau » permettent en fait de manipuler des séquences :

- dont les éléments sont de même type ;

- dont la taille est fixée à la création, on enrichit parfois le type tableau d'une ou plusieurs opérations permettant de modifier sa taille. Mais leurs utilisations doivent être rares. Si la longueur de la séquence doit souvent varier, il est souvent préférable de considérer une liste.

Signature

La signature du type tableau est la suivante :

Nom Tableau

Utilise élément, entier

Opérations

tableau

: entier x élément

→ tableau

taille

: tableau

→ entier

lire

: tableau x entier

→ élément

changer

: tableau x entier x élément

→ tableau

La syntaxe étant peu pratique, nous en définirons une plus proche de celle utilisée dans différents langages de programmation. Ainsi,

- r ← t[4] permet d'associer à une variable r la valeur de l'élément se trouvant à l'indice 4 du tableau t. Cette écriture se substitue donc à l'instruction r ← lire(t,4) ;

- t[4] ← a permet de modifier la valeur de l'élément se trouvant à l'indice 4 du tableau t en lui attribuant la valeur de la variable a. Cette écriture se substitue donc à l'instruction t ← changer(t,4,a).

Axiomatique

Voici quelques axiomes définissant dans un langage logique l'ensemble des primitives :

Exemples

La suite d'instructions suivantes :

1. t + tableau[5](0);

2. t[4] ← 10;

3. t[3] ← 2·[4];

a pour conséquence de créer un tableau d'entiers de taille 5 indicé de 1 à 5 dont la valeur est successivement :

1. 1  2   3   4  5

2. t = (0, 0,  0,  0, 0)

3. t = (0, 0,  0, 10, 0)

4. t = (0, 0, 20, 10, 0)

Remarque

Afin d'obtenir une définition simple cohérente du tableau avec celle de la liste, le premier indice d'un tableau t est l'entier 1. Ainsi le ie élément (son rang) est l'élément d'indice i.

Ce choix diffère de celui fait en langage C : le premier élément d'un tableau a pour indice 0. La raison est de pouvoir manipuler adresse et indice aisément : en C, l'adresse de t[i] n'est autre que la somme de t+i.

Si vous le souhaitez, il est possible d'enrichir le type tableau en définissant une opération tableau qui permet de choisir comme premier indice d'un tableau n'importe quel entier positif ou nul, voire n'importe quel entier relatif, voire n'importe quel caractère.

Remarque

Le terme tableau a souvent un autre sens : celui issu de langages de programmation tels que le langage C. En effet une implémentation très courante d'un tableau est d'utiliser un tableau, c'est-à-dire une zone mémoire où les éléments seront à des adresses correspondant à leur rang dans la séquence. Ainsi, en codant un entier sur 4 octets, la séquence-tableau (23, 12, 34, 56,3) sera codée sur 5 * 4 octets : si le premier élément 23 et à l'adresse 23002101, les éléments 12, 34, 56 et 3 seront aux adresses respectives 23002105, 23002109, 23002113 et 23002117.

La conséquence pratique de ce choix est pouvoir accéder à un élément à partir de son rang (ou indice) en temps constant. Ainsi, quand on évoque un tableau, on pense souvent à des opérations de lecture et d'écriture en temps constant.

2-2-2 - La structure

Le second type abstrait « séquence » est le type structure. Les opérations « structurent » permettent en fait de manipuler des séquences :

- dont les éléments sont de types différents ;

- dont la taille est fixée à la création.

On dit qu'une structure est composée de champs qui ont chacun un nom et un type.

Signature

Soient n types abstraits E_1,… , En, ainsi qu'un type « identifiant » Id, une définition du type structure peut être :

Nom structure

Utilise Id, E_1,… , En

Opérations

structure

: Id x … x Id x E_1… x En

→ structure

lire_1

: structure

→ E_1

…

liren

: structure

→ En

changer_1

: structure x E_1

→ structure

…

changern

: structure x En

→ structure

La syntaxe étant peu pratique, nous en définirons une autre. Ainsi :

- pour tout entier se substitue à  ;

- pour tout entier se substitue à .

Axiomatique

Les axiomes du type structure sont laissés en exercice.

Exemples

La suite d'instructions suivantes :

t ← structure[abs,ord](1.0 , 2.0);
t.abs ← 3.0;
t.ord ← t.ord + t.abs;

a pour conséquence de créer une structure t ayant deux champs d'identifiants abs et ord de types réels ; la structure est successivement égale à :

t = ( 1.0 , 2.0 )
t = ( 3.0 , 2.0 )
t = ( 3.0 , 5.0 )

2-2-3 - La pile

Une pile est une séquence dont toutes les opérations se font à une extrémité appelée la tête.

Signature

La signature du type pile est la suivante :

Nom pile

Utilise élément

Opérations

estVide

: pile

→ booléen

pileVide

→ pile

tête

: pile

→ élément

empiler

: pile x élément

→ pile

dépiler

: pile

→ pile

Axiomatique

Voici quelques axiomes définissant dans un langage logique l'ensemble des primitives :

Exemples

La suite d'instructions suivante :

1. p ← empiler(pileVide(),10);

2. a ← tête(p);

3. p ← empiler(p,20);

4. b ← tête(p);

5. p ← empiler(p,30);

6. c ← tête(p);

7. p ← dépiler(p);

8. d ← tête(p);

a pour conséquence de créer une pile p et un entier a de valeurs successivement égales à :

1. p = (10)         a = 10

2. p = (20,10)      b = 20

3. p = (30,20,10)   c = 30

4. p = (20,10)      d = 20

Remarques

En fonction des problèmes à résoudre ou des algorithmes à écrire, on peut ajouter ou remplacer des primitives par de nouvelles. À titre d'exemple, on peut supposer l'existence d'une opération fournissant la longueur de la séquence :

taille : pile → entier

ou une autre qui retire la tête de la pile :

extraireTête : pile → élément x pile

dont la définition algorithme pourrait simplement être :

fonction extraireTête(p:pile) : élément x pile
retourner(tête(p),dépiler(p))

2-2-4 - La file

Une file est une séquence dont toutes les opérations se font aux deux extrémités :

- la suppression et la lecture à la première extrémité ;

- l'ajout à la dernière extrémité.

Signature

La signature du type file est la suivante :

Nom file

Utilise élément, booléen

Opérations

estVide

: file

→ booléen

fileVide

:

→ file

1erÉlément

: file

→ élément

défiler

: file

→ file

enfiler

: file x élément

→ file

Axiomatique

Voici quelques axiomes définissant dans un langage logique l'ensemble des primitives :

Exemples

La suite d'instructions suivante :

1. f ← enfiler(fileVide(),10);

2. a ← 1erÉlément (f);

3. f ← enfiler(f,20);

4. b ← 1erÉlément (f);

5. f ← enfiler(f,30);

6. c ← 1erÉlément (f);

7. f ← défiler(f);

8. d ← 1erÉlément (f);

a pour conséquence de créer une file f et des entiers de valeurs successivement égales à :

1. f = (10)         a = 10

2. f = (10,20)      b = 10

3. f = (10,20,30)   c = 10

4. f = (20,30)      d = 20

2-2-5 - La liste

Une liste est une séquence munie d'opérations qui permettent d'accéder à chacun des éléments à partir de leur position (ici un rang) et qui modifient la séquence à partir d'insertion ou de suppression.

Signature

La signature du type liste est la suivante :

Nom liste

Utilise élément, entier, booléen

Opérations

estListeVide

: liste

→ booléen

listeVide

:

→ liste

ièmeElmt

: liste x entier

→ élément

insérer

: élément x entier x liste

→ liste

supprimer

: liste x entier

→ liste

longueur

: liste

→ entier

Axiomatique

Voici quelques axiomes définissant dans un langage logique l'ensemble des primitives :

Exemples

La suite d'instructions suivante :

1. l ← insérer(10,1,listeVide());

2. l ← insérer(20,2,l);

3. l ← insérer(30,3,l);

4. l ← insérer(40,2,l);

5. a ← ièmeElmt(l,1);

6. b ← ièmeElmt(l,2);

7. l ← supprimer(3,l);

a pour conséquence de créer une file l et des entiers de valeurs successivement égales à :

1. l = (10)

2. l = (10,20)

3. l = (10,20,30)

4. l = (10,40,20,30)

5. a = 10

6. b = 40

7. l = (10,40,30)

2-3 - Conclusion

Nous avons présenté dans ce cours des types comme des ensembles d'opérations définies logiquement. Nous verrons dans le prochain chapitre comment les implémenter à l'aide de deux types le type tableau et le type structure qui sont fournis par la plupart des langages de programmation.

Cette approche logique ne suffit pas, si nous souhaitons étudier la complexité en temps des algorithmes, il nous faut définir un modèle de calcul réaliste qui garantisse un faible coût en temps des primitives considérées. Ce sera l'objet d'un prochain chapitre.

3 - Chapitre 3 - Implémentations de types

Nous verrons ici quelques exemples d'implémentations d'objets.

3-1 - Types primitifs et effets de bord

3-1-1 - Types primitifs

Les types primitifs correspondent à des objets pouvant être codés sur des blocs mémoire de taille fixe. Ils permettent de représenter les quantités numériques que sont les booléens, les entiers, les rationnels, les réels. Conséquence de la taille fixe de leurs représentations en mémoire, toutes les opérations les concernant (∨, ≠, ∧, +, ·, log, sin, etc.) sont supposées être de complexité en temps constant.

Nous supposerons admise leur définition.

Insistons sur un point : tout type primitif est représenté à l'aide d'un nombre fixe d'octets. Ainsi, définir un type entier à l'aide d'un type primitif suppose que l'on se restreint à un nombre fini d'entiers (sur un octet l'ensemble d'entiers représentables est [0, 2^8-1], sur 4 octets il s'agit de [0, 24·8-1]). En conséquence de quoi, si vous souhaitez manipuler des entiers n de taille non arbitrairement fixée, il est nécessaire de les représenter à l'aide d'un type non primitif, par exemple une liste de longueur . Le coût des opérations ne pourra pas être considéré comme constant, mais dépendra alors de la longueur des listes.

Seront considérés comme non primitifs les types tableau, structure et tous les types construits à partir de ceux-ci notamment tous les types permettant de représenter des ensembles.

3-1-2 - Effets de bord

Nous avons présenté des types permettant de manipuler des ensembles d'objets qu'ils soient ordonnés ou non (ensembles, séquences, et bientôt arbres). Ces ensembles nécessitent trivialement un espace mémoire de taille non constante (contrairement aux booléens, « petits » entiers et « petits » réels).

Nous avons défini pour ces objets de grande taille des opérations permettant de les modifier (par exemple dépiler pour la pile, ajouter pour l'ensemble, insérer pour une liste).

Une alternative s'offre à nous.

Opérations de complexité en temps faible, voire constant

Considérons l'exemple de l'opération dépiler du type pile et l'instruction : p ← dépiler(q);.

Il est possible de fournir une implémentation en temps constant (voir section prochaine). Or en temps constant, il est impossible de recopier l'espace mémoire utilisé par la pile q, éventuellement très grand ; en d'autres termes, la pile p utilise pour totalité ou presque totalité la zone mémoire de q et ce, quelle que soit l'implémentation d'une pile et de la fonction dépiler. En conséquence de quoi, une modification ultérieure de q entraînera sûrement une modification de p.

Il est par exemple possible qu'après exécution de p ← dépiler(p); les piles p et q soient égales, ou sinon aient les mêmes éléments.

Ceci remet en cause la définition axiomatique définissant les piles. Un choix à peine contraignant pour garantir les axiomes est de prendre pour membre droit d'une instruction uniquement la variable prise en argument et d'imposer ainsi comme seules instructions possibles :

q ← dépiler(q);

Nous verrons que sous cette hypothèse dépiler(q) peut s'exécuter en temps constant. Ainsi, l'algorithme suivant qui cherche la présence d'un élément e dans une pile p

1. fonction appartient(e:élément; p : pile) : booléen

2. tantque non(estVide(p))

3. si tete(p)=e

4. retourner vrai();

5. p ← dépiler(p);

7. retourner faux();

a une complexité en temps (avec n = taille(p)) et en espace . Nous définirons dans le prochain chapitre un modèle de calcul complet et verrons dans cet exemple que la pile p après exécution de appartient(e,p) n'est pas modifiée.

Si vous souhaitez créer une nouvelle pile p obtenue en dépilant une pile q, il faut alors réaliser une copie préalable de q qui crée une pile ayant les mêmes éléments, mais utilisant une zone mémoire disjointe de celle utilisée par q. La complexité en temps de cette opération est bien sûr linéaire : c'est-à-dire proportionnelle au nombre d'octets nécessaire à la représentation de q. La suite d'instructions devient alors :

p ← dépiler(copie(q));

Sous ces conditions, puisque les zones mémoire associées à p et q ne partagent aucun octet, aucune modification de p n'entraîne de modification de q et inversement.

Opérations de complexité en temps linéaire

Une autre solution consisterait lorsque l'on définit l'opération dépiler de systématiquement réaliser une copie de l'ensemble (ici une pile) passé en argument. Cela aurait l'avantage de pouvoir exécuter l'instruction

p ← dépiler(copie(q));

sans craindre qu'une modification ultérieure de p ne modifie q (et inversement).

L'intérêt est logique : les axiomes sont garantis. Mais l'utilité de par exemple dépiler est réduit.

Ainsi, l'algorithme suivant qui cherche la présence d'un élément e dans une pile p

1. fonction appartient(e:élément; p : pile) : booléen

2. tantque non(estVide(p))

3. si tete(p)=e

4. retourner vrai();

5. p ← dépiler(p);

7. retourner faux();

a une complexité en temps (avec n = taille(p)) et en espace .

3-2 - Tableau infini

En introduction de ce cours, nous avons vu comment l'objet « séquence » pouvait être représenté en mémoire selon une zone mémoire contiguë qui permet l'accès à un élément selon son rang en temps constant ou selon un chaînage avec un accès en temps non constant.

Contrairement au principe qui souhaite ne pas mélanger la définition du type abstrait de son implémentation, les usages courants en algorithmique font que tout type abstrait « tableau » désigne un type séquence implémenté selon une zone contiguë.

Un exemple fameux de type tableau est tableauInfini dont la signature est :

Nom tableaulnfini

Utilise entier, élément

Opérations

tableaulnfini

: élément

→ tableaulnfini

ième

: tableaulnfini x entier

→ élément

changerIème

: tableaulnfini x entier x élément

→ tableaulnfini

Définir un tableau infini est fait simplement à l'aide d'une structure contenant deux champs :

1. Un premier champ de nom tab de type tableau ;

2. Un second champ de nom val contenant la valeur de type élément apparaissant une infinité de fois.

La figure 3.1 fournit une définition du constructeur tableauInfini.

FIG. 3.1 - Définition de tableauInfini

1. fonction tableaulnfini(e: élément) : structure

2. t ← tableau[e](100);

3. retourner structure(tab,val)(t,e);

La définition de ième ne pose aucune difficulté :

1. fonction ième(t:tableaulnfini , i: entier): élément

2. si i ≤ taille(t.tab) alors

3. retourner t.tab[i];

4. sinon

5. retourner t.val;

Voici une implémentation de changerIème :

1. fonction changerIème(t:tableaulnfini,i:entier,e:élément):tableaulnfini

2. t ← extensionÉventuelle(t,i);

3. t.tab[i] ← e;

4. retourner t;

où extensionEventuelle est ainsi défini :

1. fonction extensionÉventuelle(t:tableaulnfini,i:entier) :tableaulnfini

2. si i ≤ taille(t.tab)

3. retourner t;

4. sinon

5. ntaille ← stratégieExtension(taille(t.tab),i);

7. u ← tableau(ntaille)(t.val);

9. pour i + 1 à taille(t.tab)

10. u[i] ← t.tab[i];

12. t.tab ← u;

14. retourner t;

Dès que l'on souhaite modifier la valeur d'un élément se trouvant au-delà du tableau fini tab, on étend ce tableau à une taille au moins égale à cet indice. Trois stratégies définies par la fonction stratégieExtension se présentent alors :

1. Soit on fait du juste mesure. On étend le tableau exactement de ce dont on a besoin. Plus formellement nous avons :

fonction stratégieExtension(n:entier,i:entier):entier
retourner i;

2. On peut affiner cette méthode en l'étendant à l'indice désiré, mais à l'indice immédiatement supérieur multiple d'une constante fixée, par exemple égale à 100. Plus formellement nous avons :

fonction stratégieExtension(n:entier,i:entier):entier
retourner ⌈ i/100 ⌉;

3. Soit on anticipe des besoins futurs de façon à limiter le nombre de telles extensions. Une stratégie efficace consiste à systématiquement doubler la taille du tableau. Plus formellement nous avons :

1. fonction stratégieExtension(n:entier,i:entier):entier

2. nt ← n;

4. faire

5. nt ← nt · 2;

6. jusqu'à nt ≥ i

8. retourner nt;

Exemple 6 Ainsi l'algorithme :

1. t ← tableaulnfini(0);

2. pour i de 1 à n

3. t ← changerIème(t,i,i·2);

réalisera

1. n extensions selon la première stratégie. La complexité en temps cumulée est . Ceci est toujours extrêmement coûteux. Cette stratégie doit être abandonnée ;

2. n/100 extensions selon la seconde (dans le cas où la constante est 100). La complexité en temps cumulée est . Cette stratégie est théoriquement identique à la première, mais peut être employée dans certains algorithmes ;

3. extensions selon la troisième. La complexité en temps cumulée est , c

4. ar égale à . Cette stratégie est pour cette raison préférable aux deux précédentes.

3-3 - Représentation d'une pile par une zone mémoire contiguë

Une utilisation immédiate d'un tableau infini est l'implémentation d'une pile.

Nom pile

Utilise élément

Opérations

pileVide

:

→ pile

estVide

: pile

→ booléen

empiler

: pile x élément

→ pile

dépiler

: pile

→ pile

tête

: pile

→ élément

Et ce, sous la forme d'une structure ayant deux champs, ce tableau ainsi que l'indice de l'élément au sommet de la pile, l'indice étant égal à 0 si la pile est vide.

1. fonction pileVide() :pileRéel

2. t ← tableauInfini(0.0);

3. retourner structure(tab,ind)(t,0);

5. fonction empiler(p:pileRéel, r:réel):pileRéel

6. p.ind ← p.ind + 1;

7. p.tab ←  changerIème(p.tab,p.ind,r);

8. retourner p;

Exercice 1 Écrire les autres primitives.

Remarque 2 Conformément au modèle présenté lors du dernier chapitre, les piles sont des types non primitifs. Ainsi, l'algorithme

1. fonction test () :booléen

2. p ← pileVide();

3. q ← p;

4. q ← empiler(q, 1.5);

5. retourner (estVide(q));

retourne faux.

En effet, les objets de types non primitifs p et q partagent toujours la même référence donc désignent toujours le même objet égal à la fin à la pile contenant l'unique réel 1.5 : l'affectation q ← p; qui fait en sorte que les deux objets de types non primitifs p et q partagent la même référence, donc désignent le même objet, l'instruction suivante q ← empiler(q, 1.5); ne modifie pas la référence de q qui reste donc égale à celle de p.

Remarque 3 Si l'on souhaite à partir d'une pile p définir une pile q ayant les mêmes éléments, mais dont aucune modification sur p n'entraîne de modification sur q, il nous faut nécessairement réaliser une « copie » de la première, et ce, dans une zone mémoire disjointe de la seconde.

Exercice 2 Écrire une telle fonction copie.

3-4 - Représentation d'une liste itérative à l'aide d'un chaînage

Une définition du type abstrait liste est la suivante :

Nom liste

Utilise élément, entier

Opérations

estListeVide

: liste

→ booléen

listeVide

:

→ liste

ièmeElmt

: liste x entier

→ élément

insérer

: élément x entier x liste

→ liste

supprimer

: entier x liste

→ liste

longueur

: liste

→ entier

3-4-1 - Encapsulation du type élément dans un nœud

Une première idée qui sera réutilisée dans le cas d'objets plus complexes, tels les arbres, est de définir un nouveau type abstrait, le type nœud, qui encapsule le type élément. Cette définition complexifie la définition du type liste en nécessitant de définir le nouveau type abstrait nœud. Ce coût initial est largement compensé par la simplicité des algorithmes implémentant les différentes primitives comme nous le verrons plus loin. Voici la signature d'un tel type :

Nom nœud

Utilise élément, booléen

Opérations

constructNœud

: élément x nœud

→ nœud

?suivant

: nœud

→ booléen

suivant

: nœud

→ nœud

contenu

: nœud

→ élément

changerCont

: nœud x élément

→ nœud

changerSuiv

: nœud X nœud

→ nœud

L'implémentation d'un tel objet est réalisée à l'aide d'une structure contenant deux champs :

1. Un champ de nom cont de type élément ;

2. Un champ de nom suiv désignant le nœud suivant.

Voici l'écriture de quelques primitives :

1. fonction constructNœud(e :élément, n:nœud) :nœud

2. retourner structure(cont,suiv)(e,n);

4. fonction changerSuiv(n:nœud,p:nœud) :nœud

5. n.suiv ← p;

6. retourner n;

3-4-2 - Sentinelle avant

Si l'on souhaite insérer un élément e en ie position, deux cas apparaissent selon que i est égal à 1 ou non :

- si i = 1, le nouveau premier nœud est celui contenant cet élément e ;

- si i ≠ 1, le premier nœud est inchangé.

Cette singularité i= 1 complexifie cet algorithme. Il est facile de se douter que d'autres algorithmes le seront aussi.

Une seconde idée permet de simplifier l'écriture de nombreux algorithmes. Elle consiste à utiliser une « sentinelle avant » : l'idée étant de représenter en mémoire la liste (3,5) par une liste composée de trois éléments (#,3,5), la valeur du premier élément n'ayant aucune importance quant à la valeur de la liste représentée : cet élément s'appelle la sentinelle avant.

Ainsi, une liste sera représentée par un type structure contenant un unique champ de nom sentinelleAvant et désignant cette sentinelle avant.

Pour des raisons similaires, il est souhaitable de rajouter une sentinelle arrière.

Supposons donc enrichi le type nœud de façon à pouvoir produire des nœuds sentinelles et à pouvoir tester si un nœud est une sentinelle. En d'autres termes, supposons les opérations :

sentinelle

:

→ nœud

?sentinelle

: nœud

→ booléen

Ainsi, la fonction listeVide peut se définir comme suit :

1. fonction listeVide():liste

2. n ← sentinelle();

3. n ← changerSuivant(n,sentinelle());

4. retourner structure (sentinelleAvant)(n);

Une fonction très utile de nom ièmeNœud permet à partir d'une liste et d'un entier i de retourner son ie nœud (le nœud sentinelle si i = 0). La fonction ièmeNœud peut ainsi être définie :

1. fonction ièmeNœud(l:liste; i:entier) :nœud

2. n ← l.sentinelleAvant;

4. pour i ← 1 à i faire

5. n ← suivant(n);

7. retourner n;

Il en découle les définitions des primitives ième et insérer (Figures 3.2 et 3.3).

FIG. 3.2 - Fonction ième

1. fonction ième(l:liste;i:entier) :élément

2. retourner contenu(ièmeNœud(l,i));

FIG. 3.3 - Fonction insérer

1. fonction insérer(l:liste,i:entier,e:élément):liste

2. prec ← ièmeNœud(l,i-1);

3. n ← constructNœud[e,suivant(prec)](cont, suiv);

4. prec ← changerSuiv(prec,n);

6. retourner l;

Exercice 3 Écrire la fonction supprimer.

Exercice 4 Indiquer comment singulariser un nœud comme nœud sentinelle.

En d'autres termes, écrire les primitives sentinelle et ?sentinelle.

3-4-3 - Autre attribut de la liste : sa longueur

Si l'algorithme le requiert, pour simplifier ou optimiser l'algorithme nous pouvons définir de nouveaux attributs au type liste.

Nous pouvons par exemple implémenter le type liste de façon à ce que le calcul de la longueur se fasse en temps constant.

Pour cela :

1. Nous enrichissons le type abstrait de la fonction : longueur liste → entier ;

2. Nous ajoutons dans la structure implémentant la liste un champ longueur initialisé à 0 et modifié lors de toute modification de la liste.

La fonction listeVide peut se définir ainsi :

1. fonction listeVide() liste

2. n ← sentinelle();

3. n ← changerSuivant(a,sentinelle());

5. retourner structure(sentinelleAvant,longueur)(n,0);

Exercice 5 Écrire les autres primitives du type liste.

3-4-4 - Un autre attribut de la liste : le curseur

L'exécution de la fonction test de la Figure 3.4 double la valeur de chaque élément entier d'une liste l ; il a une complexité en temps en , puisque l'exécution de ièmeNœud(l,i) est égale à .

FIG. 3.4 - Parcours d'une liste

1. fonction test(l:liste) : liste

2. n ← taille(l);

4. pour i ← 1 à n

5. p ← ièmeNœud(l,i);

6. p ← changerCont(p,2·contenu(p));

8. retourner l;

Certes, on aurait pu réécrire l'algorithme en parcourant les nœuds de proche en proche et obtenir un algorithme linéaire. Mais nous allons montrer qu'une meilleure implémentation permet d'obtenir une complexité en temps linéaire sans modifier l'algorithme.

Cette idée consiste à ajouter à l'implémentation de la liste un nœud curseur (nom du champ curseur) ainsi que son rang (nom du champ rangCurseur). Ce curseur est positionné sur le ie nœud à chaque appel de la fonction ièmeNœud.

Ainsi, si le curseur est le nœud de rang i (le ie nœud) d'une liste l, la complexité en temps de l'exécution de ièmeNœud sur l'entrée l et i+1 (voire i, i+2) est constant et non plus .

L'écriture de ièmeNœud est alors :

1. fonction ièmeNœud(l:liste;i:entier) :nœud

2. si l.rangCurseur ≤ i

3. n ← n.curseur;

4. j ← n.rangCurseur;

5. sinon

6. n ← l.sentinelleAvant;

7. j ← 0;

9. tantque j < i faire

10. n ← suivant(n);

11. j ← j + 1;

13. l.curseur ← n;

14. l.rangCurseur ← i;

16. retourner n;

En conséquence de quoi, il est facile d'observer que la fonction test de la Figure 3.4 a une complexité en temps égale non pas à mais .

Exercice 6 Écrire les autres primitives du type liste selon que le type nœud présente un simple ou un double chaînage.

3-4-5 - Implémentation du type liste

Implémenter le type liste se fait en utilisant un type structure composé des champs :

- s ;

- c ;

- rangC ;

- longueur.

Les différentes fonctions se définissent ainsi :

1. fonction estVide(l : liste) : booléen

2. retourner l.longueur = 0;

4. fonction longueur(l : liste) : entier

5. retourner l.longueur;

7. fonction listeVide() : liste

8. n ← sentinelle();

9. n ← changerSuivant(a,sentinelle());

10. retourner structure(sentinelleAvant,curseur,indiceCurseur, longueur)

11. (n,              n,      0,             0);

13. fonction ièmeElmt(l : liste; i : entier) : élément

14. retourner contenu(ièmeNœud(1, i))

16. fonction supprimer(l : liste; i : entier) : liste

17. n ← ièmeNœud(l,i-1);

18. n ← changerSuivant(n,suivant(n));

19. retourner l;

21. fonction insérer(e : élément; i : entier; l : liste ) : liste

22. n ← ièmeNœud(l,i-1);

23. ajout ← constructNœud(e,suivant(n));

24. n ← changerSuiv(n,ajout);

26. retourner l;

3-4-6 - Implémentation d'un nouveau type liste

Il est possible de repenser totalement la définition du type abstrait, c'est-à-dire du nombre et du sens de chacune des opérations en fonction des concepts introduits. Ceci permet d'écrire des algorithmes en utilisant des routines de bas niveau manipulant ici par exemple des curseurs et permettant d'évaluer très précisément la complexité de ces algorithmes.

Voici, un exemple de nouvelle signature :

Nom nouvelleListe

Utilise nœud, entier, booléen

Opérations

estVide

: nouvelleListe

→ booléen

listeVide

: nouvelleListe

→ nouvelleListe

curseur

: nouvelleListe

→ nouvelleListe

rangCurseur

: nouvelleListe

→ entier

debut

: nouvelleListe

→ nouvelleListe

fin

: nouvelleListe

→ nouvelleListe

avant

: nouvelleListe

→ nouvelleListe

tropADroite

: nouvelleListe

→ booléen

où la signification des opérations est ainsi « vulgairement » définie :

- début (fin) positionne le curseur sur le premier (resp. dernier) nœud ;

- avant avance le curseur ;

- tropADroite indique si le curseur a débordé de la dernière position.

Exercice 7 Définir un type nœud permettant d'implémenter en temps constant une opération arrière:liste → liste qui permet de reculer le curseur.

Remarque

La liste d'opérations définissant le type nouvelleListe est fournie à titre d'exemple. On peut la modifier en ajoutant par exemple des opérations du type liste comme ièmeElmt, de nouvelles opérations comme ièmeNœud, avancerIèmeRang etc. Il est inutile de vouloir définir un type liste universel, car le nombre d'opérations serait trop élevé. Le choix de ces opérations est dicté par le problème à résoudre et l'algorithme à écrire.

3-5 - Conclusion

Nous avons présenté quelques principales améliorations possibles au type abstrait ou à son implémentation. Une amélioration parfois utile est de pouvoir parcourir la liste dans les deux sens.

Cela se fait simplement en enrichissant le type nœud en permettant l'accès au nœud précédent par ajout des fonctions :

?prec

: nœud

→ booléen

preced

: nœud

→ nœud

changerPrec

: nœud x nœud

→ nœud

et d'ajouter dans la structure un nouveau champ prec.

Cette liste d'amélioration n'est pas exhaustive. Vu leur nombre, il est fastidieux d'intégrer toutes les fonctionnalités dans un même type. Le choix des fonctions accessibles et de leur implémentation doit être réalisé en fonction du problème à résoudre et de l'algorithme à écrire.

4 - Chapitre 4 - Arbres binaires

Une façon très courante de représenter un ensemble est d'utiliser non une séquence, mais une arborescence, c'est-à-dire une structure bidimensionnelle accessible à partir d'un premier élément appelé la racine et qui permet d'accéder de façon récursive de père en fils à chacun des éléments d'une unique façon.

Cette structure récursive permet d'implémenter les ensembles en obtenant des primitives de complexité très faible (en temps logarithmique).

Afin de simplifier, nous nous intéresserons à une sous-classe des arborescences, les arbres binaires.

4-1 - Définition

Une définition simple d'un arbre binaire est sa définition récursive :

Définition 1 (Arbre binaire) Un arbre binaire T est :

soit l'arbre vide, noté  ;

soit un triplet (r, g, d) où :

- r est un nœud, appelé la racine de T, noté rac(T),

- g est un arbre binaire, appelé le sous-arbre gauche de T, noté ga(T),

- d est un arbre binaire, appelé le sous-arbre droit de T, noté dr(T).

Définition 2 (Père, frère…) La racine d'un arbre T est le père de la racine du sous-arbre gauche (resp. droit) si celle-ci existe. Deux nœuds ayant même père sont déclarés frères. L'ascendant d'un nœud est son père ou un ascendant de celui-ci. La distance d'une racine à un nœud est le nombre d'ascendants de ce dernier. Une feuille est un nœud sans fils.

Définition 3 (Hauteur) La hauteur d'un arbre est la plus grande distance d'un nœud à la racine : un arbre ayant pour unique sommet sa racine est de hauteur nulle.

Un premier type abstrait découlant de cette définition est le suivant :

Nom Arbre

Utilise élément, entier, booléen

Opérations

estVide

: Arbre

→ booléen

arbreVide

:

→ Arbre

arbreGauche

: Arbre

→ Arbre

arbreDroit

: Arbre

→ Arbre

racine

: Arbre

→ élément

consArbre

: élément x Arbre x Arbre

→ Arbre

Ce premier type abstrait a l'avantage de sa simplicité, il pourra donc être utilisé dans certaines premières définitions d'algorithme. Mais, si l'on souhaite écrire des algorithmes avancés et évaluer leur complexité en temps et en espace, il souffre des mêmes limites rencontrées par le type abstrait liste à l'opposé de nouvelleListe.

4-2 - Arbre binaire parfait

Définition 4 Un arbre binaire de hauteur est parfait s'il est complètement rempli sur tous les niveaux, sauf parfois, le plus bas qui est rempli en partant de la gauche jusqu'à un certain point.

Supposons que nous ayons à implémenter des arbres binaires parfaits. Une solution serait de considérer n'importe quelle implémentation d'arbre binaire : qui peut le plus peut le moins. Ceci peut être une erreur, car cette implémentation ne bénéficierait pas des singularités d'un arbre parfait.

Les seules modifications autorisées d'un arbre binaire parfait sont ou de modifier le contenu d'un nœud, ou de supprimer le dernier nœud (le plus à droite sur le dernier niveau) ou d'ajouter un nœud à la « suite » du dernier le plus à droite sur le dernier niveau (ou si celui-ci est rempli) d'en ajouter un le plus à gauche sur le nouveau dernier niveau.

Une implémentation consiste à utiliser un tableau dont la taille est égale à la taille n de l'arbre (c'est-à-dire son nombre de nœuds) ayant pour ensemble d'indices [1,n] de telle sorte que :

1. Le nœud racine est l'indice 1 ;

2. Le nœud fils gauche d'un nœud i est 2 · i ;

3. Le nœud fils droit d'un nœud i est 2 · i + 1.

Exemple 7 Ainsi l'arbre binaire parfait suivant :

a pour représentation le tableau suivant :

On observe que le nœud d'élément 24 a pour fils gauche le nœud d'élément 45 ; leur indice respectif dans le tableau est 3 et 6 et vérifie : 3cot 2 = 6.

4-3 - Implémentation chaînée d'un arbre binaire

Pour les mêmes raisons qui nous ont amené à définir une liste comme une séquence de nœuds mutuellement chaînés, nous définissons un arbre comme un ensemble de nœuds mutuellement chaînés.

Les définitions que nous présentons ici ne sont pas universelles, elles peuvent évoluer selon le problème à résoudre ou l'algorithme à écrire. À l'image du type nouvelleListe, la définition du type arbre repose sur la définition du type abstrait nœud.

Nom arbre

Utilise nœud, entier, booléen

Opérations

estVide

: arbre

→ booléen

arbreVide

:

→ arbre

racine

: arbre

→ nœud

prendreRacine

: nœud

→ arbre

Une définition du type nœud peut être la suivante :

Nom nœud

Utilise élément, booléen

Opérations

contenu

: nœud

→ élément

?filsGauche

: nœud

→ booléen

?filsDroit

: nœud

→ booléen

filsGauche

: nœud

→ nœud

filsDroit

: nœud

→ nœud

estSentinelle

: nœud

→ booléen

constructSentinelle

:

→ nœud

constructNœud

: élément x nœud x nœud

→ nœud

changerFilsGauche

: nœud x nœud

→ nœud

changerFilsDroit

: nœud x nœud

→ nœud

changerContenu

: nœud x élément

→ nœud

Afin de rendre plus lisibles les algorithmes en définissant de nouvelles opérations obtenues en dégradant l'opération constructNœud. Voici de nouvelles opérations possibles :

Utilise élément, booléen

Opérations(suite)

changerFilsGauche

: nœud x nœud

→ nœud

changerFilsDroit

: nœud x nœud

→ nœud

changerContenu

: nœud x élément

→ nœud

Le type défini ici ne permet en fait que de parcourir l'arbre de haut en bas (de la racine vers les feuilles). On peut souhaiter pouvoir accéder à partir d'un nœud à son père. Il nous faut alors rajouter les opérations suivantes :

Utilise booléen

Opérations(suite)

?père

: nœud

→ booléen

père

: nœud

→ nœud

changerPère

: nœud x nœud

→ nœud

et modifier bien sûr en conséquence le constructeur nœud constructNœud dont la nouvelle signature doit être :

constructNœud

: élément x nœud x nœud x nœud

→ nœud

4-3-1 - Définitions des primitives

Un arbre peut ainsi être défini à l'aide d'une structure composée d'un unique champ :

- de nom racine de type nœud.

Ce qui fournit la primitive suivante :

fonction racine(t : arbre) : nœud
retourner t.racine;

Dans le cas singulier de l'arbre vide (qui ne contient ni nœud, ni racine), une représentation simple est de le représenter à l'aide d'un nœud qui est une sentinelle :

1. fonction arbreVide() : arbre

2. n ← constructSentinelle();

3. retourner structure(racine)(n);

5. fonction estVide(t : arbre) : booléen

6. retourner estSentinelle(t.racine);

8. fonction prendreRacine(n : nœud) : arbre

9. retourner structure(racine)(n);

Un nœud peut être défini à l'aide d'une structure composée de cinq champs :

- un champ de nom cont de type élément ;

- trois champs de noms gauche, droit, père de type nœud ;

- un champ de nom sent de type booléen indiquant si c'est une sentinelle.

Il en découle les définitions suivantes :

1. fonction constructNœud(e : élément; g,d,p : nœud ) : nœud

2. retourner structure(cont,gauche,droit,père,sent)(e,g,d,p,faux());

4. fonction constructSentinelle() : nœud

5. retourner structure(cont,gauche,droit,père,sent)(0,0,0,0,vrai());

7. fonction estSentinelle(n : nœud) : booléen

8. retourner n.sent;

10. fonction ?filsGauche(n : nœud) : booléen

11. retourner estSentinelle(filsGauche);

13. fonction changerFilsDroit(n,droit : nœud) : nœud

14. n.droit ← droit;

15. retourner n;

5 - Chapitre 5 - Parcours d'arbres

Un parcours d'arbres est un algorithme qui permet de visiter chacun des nœuds de cet arbre. Il existe plusieurs façons de les parcourir. Nous en présentons ici deux. Ces techniques concernent en fait tous les arbres. En vue de simplifier cet exposé, nous les présenterons sur des arbres binaires.

La première est familière à une définition récursive de l'arbre. Il s'agit du parcours en « profondeur » qui consiste à définir le parcours d'un arbre comme le parcours de son sous-arbre gauche augmenté du parcours de son sous-arbre droit. Ce parcours défini ici récursivement admet une écriture algorithmique équivalente itérative utilisant une Pile.

La seconde consiste à parcourir les nœuds de l'arbre en traitant prioritairement les nœuds les plus proches de la racine. Ce parcours est appelé parcours en largeur. Nous verrons comment écrire itérativement un tel parcours à l'aide d'une file.

5-1 - Parcours en profondeur

L'algorithme de parcours en profondeur est défini en utilisant une fonction

1. procédure parcoursArbreProfondeur(T:arbre)

2. si non(estVide(T))

3. parcoursProfondeur(racine(T));

auxiliaire parcourant récursivement les nœuds parcoursProfondeur (Figure 5.1).

L'algorithmique est générique et utilise trois fonctions auxiliaires traiter1, traiter2, traiter3. Afin de simplifier l'exposé, nous pouvons supposer que ces opérations ne réalisent pas de modifications de la structure de l'arbre et ne réalisent qu'un calcul local au nœud traité (éventuellement, elles ne font rien).

FIG. 5.1 - Parcours en profondeur récursif

1. procédure parcoursProfondeur (n :nœud)

2. si estSentinelle(n) alors

3. traiter4(n);

4. sinon

5. traiter1(n);

6. parcoursProfondeur(filsGauche(n));

7. traiter2(n);

8. parcoursProfondeur(filsDroit(n));

9. traiter3(n);

FIG. 5.2 - Un arbre binaire

Exemple 8 Sur l'exemple de l'arbre binaire de la Figure 5.2 (les sentinelles sont indifféremment nommées s) l'exécution de l'algorithme entraîne l'exécution des instructions suivantes :

1. traiter1(n1); traiter1(n2); traiter1(n4); traiter4(s);

2. traiter2(n4); traiter4(s);

3. traiter3(n4);

4. traiter2(n2);

5. traiter1(n5); traiter4(s);

6. traiter2(n5); traiter4(s);

7. traiter3(n5); traiter3(n2);

8. traiter2(n1);

9. traiter1(n3); traiter1(n6); traiter4(s);

10. traiter2(n6); traiter4(s);

11. traiter3(n6);

12. traiter2(n3); traiter4(s);

13. traiter3(n3); traiter3(n1);

5-1-1 - Parcours préfixe, infixe ou suffixe

Il arrive parfois que le problème à résoudre nécessite un unique traitement sur chacun des nœuds (deux des trois traitements traiter1, traiter2, traiter3 consistent à ne rien faire). Nous parlons alors de parcours :

- préfixe si traiter2 et traiter3 sont des instructions vides ;

- infixe si traiter1 et traiter3 sont des instructions vides ;

- suffixe si traiter1 et traiter2 sont des instructions vides.

Exemple 9 Sur l'exemple de l'arbre précèdent, le parcours préfixe consistant à n'exécuter que les instructions traiter1 provoque l'exécution de :

1. traiter1(n1); traiter1(n2); traiter1(n4);

2. traiter1(n5);

3. traiter1(n3); traiter1(n6);

Exemple 10 Sur l'exemple de l'arbre précédent, le parcours infixe consistant à n'exécuter que les instructions traiter1 provoque l'exécution de :

1. traiter2(n4);

2. traiter2(n2);

3. traiter2(n5);

4. traiter2(n1);

5. traiter2(n6);

6. traiter2(n3);

Exemple 11 Sur l'exemple de l'arbre précédent, le parcours postfixe consistant à n'exécuter que les instructions traiter1 provoque l'exécution de :

1. traiter3(n4);

2. traiter3(n5); traiter3(n2);

3. traiter3(n6);

4. traiter3(n3); traiter3(n1);

Exemple 12 Si nous souhaitons placer dans une file les contenus des différents nœuds en utilisant un parcours préfixe, l'algorithme de parcours s'écrit ainsi :

1. fonction parcoursArbre1(T:arbre) : file

2. retourner parcours1(racine(T),fileVide());

où parcours1 est défini par la Figure 5.3.

FIG. 5.3 - Mise en séquence préfixe des nœuds

1. fonction parcoursi(n:nœud,F:file) file

2. si non(estSentinelle(n)) alors

3. F ← enfiler(contenu(n),F);

4. F ← parcoursi(filsGauche(n),F);

5. F ← parcoursi(filsDroit(n),F);

7. retourner F;

L'exécution d'un tel algorithme sur l'arbre binaire de l'exemple 5.2 retourne la file (n1,n2,n4,n5,n3,n6).

5-1-2 - Écriture itérative d'un parcours en profondeur

L'exécution d'un algorithme récursif pouvant être coûteuse en espace mémoire, il est souvent préférable de fournir une version itérative.

Une version itérative équivalente à l'algorithme parcoursArbre est celle décrite sur la Figure 5.4.

5-2 - Parcours en largeur

Un second parcours d'un arbre consiste à traiter la racine, puis ses fils, ses petits-fils et ainsi de suite. Ainsi, lors de ce parcours, sont traités les nœuds à distance 0 de la racine (la racine), puis ceux à distance 1, puis ceux à distance 2 et ainsi de suite.

La définition d'un tel parcours nécessite une file et peut être celle décrite par la Figure 5.5.

Exemple 13 Sur l'exemple de l'arbre binaire de la Figure 5.2, l'exécution de l'algorithme entraîne l'exécution des instructions suivantes :

1. traiter1(n1); traiter2(n1);

2. traiter1(n2); traiter2(n2);

3. traiter1(n3); traiter2(n3);

4. traiter1(n4); traiter2(n4);

5. traiter1(n5); traiter2(n5);

6. traiter1(n6); traiter2(n6);

FIG. 5.4 - Parcours en profondeur itératif

1. procédure parcoursArbreProfondeurItératif(T:arbre)

2. si non(estVide(T)) alors

3. P ← empiler((racine(T),0),pileVide());

5. tantque non(estVide(P)) faire

6. (n,i) ← tete(P);

7. P ← depiler(P);

9. si estSentinelle(n) alors

10. traiter4(n);

11. sinon si i=0 alors

12. P ← empiler((n,3),P);

13. P ← empiler((filsDroit(n),0),P);

14. P ← empiler((n,2),P);

15. P ← empiler((filsGauche(n),0),P);

16. P ← empiler((n,1),P);

17. sinon si i=1 alors

18. traiter1(n);

19. sinon si i=2 alors

20. traiter2(n);

21. sinon

22. traiter3(n);

FIG. 5.5 - Parcours en largeur

1. procédure parcoursLargeur(T:arbre)

2. si non(estVide(T))

3. F ← enfiler(racine(n),fileVide());

5. tantque non(estVide(F)) faire

6. n ← premier(F);

7. F ← defiler(F);

9. traiter1(n);

11. si non(estSentinelle(n)) alors

12. F ← enfiler(filsGauche(n),F);

13. F ← enfiler(filsDroit(n),F);

15. traiter2(n);

6 - Chapitre 6 - Arbres binaires de recherche

Les arbres binaires de recherche permettent d'implémenter de façon très efficace les multiensembles en permettant d'accéder à un élément en un temps qui dépend non de la cardinalité de l'ensemble, mais de la hauteur de l'arbre qui le représente.

6-1 - Définitions

Définition 5 Un arbre binaire de recherche (abrégé en A.B.R.) est un arbre binaire dans lequel la clé de tout nœud n

1. Est strictement supérieure à la clé de tout nœud du sous-arbre gauche de n ;

2. Est strictement inférieure à la clé de tout nœud du sous-arbre droit de n.

Exemple 14 Un exemple d'arbre binaire de recherche est celui décrit par la Figure 6.1.

FIG. 6.1 - Un arbre binaire de recherche

Aussi, nous supposerons que le type nœud est enrichi d'une fonction qui lui fournit la clé :

clé

: nœud

→ entier

6-2 - Le problème Recherche

Résoudre le problème de recherche :

Recherche
Entrée : un arbre T, une clé k
Sortie : un couple (b,n) formé du booléen b indiquant si T contient un nœud de clé k et si oui d'un tel éventuel nœud n

est résolu aisément à l'aide de la fonction rechercheArbre utilisant une fonction récursive recherche définie par la Figure 6.2.

FIG. 6.2 - Fonction recherche

1. fonction rechercheArbre(T:arbre,k:entier):booléen x nœud

2. retourner recherche(racine(T),k);

4. fonction recherche(n:nœud,k:entier):booléen x nœud

5. si estSentinelle(n)

6. retourner (faux,_);

7. sinon si k=clé(n)

8. retourner (vrai,n);

9. sinon si k < clé(n)

10. retourner recherche(filsGauche(n),k);

11. sinon

12. retourner recherche(filsDroit(n),k);

Exercice 8 Prouver que recherche est correct, c'est-à-dire résout le problème Recherche.

Exercice 9 Prouver que la complexité en temps dans le pire des cas de recherche est où est la hauteur de l'arbre T.

Exercice 10 Écrire de façon itérative l'algorithme recherche.

6-3 - Insertion d'un nouveau nœud

Pour insérer un nouveau nœud x dans un arbre T, on parcourt l'arbre de façon similaire à l'algorithme recherche jusqu'à trouver un nœud y sans fils gauche et de clé supérieure (resp. ou sans fils droit et de clé inférieure). À cet instant, on place x fils gauche (resp. droit) de y.

Afin de simplifier l'écriture, on supposera que le nœud n a pour père, pour fils gauche et pour fils droit trois nœuds sentinelles. L'algorithme insérer est décrit sur la Figure 6.3.

FIG. 6.3 - Insertion d'un nœud dans un A.B.R.

1. fonction insérer(T:arbre, n:nœud) arbre

2. si estVide(T)

3. retourner changerRacine(T,n);

4. sinon

5. x ← racine(T);

7. faire

8. y ← x;

9. si clé(n) < clé(x)

10. x ← filsGauche(x);

11. àGauche ← vrai();

12. sinon

13. x ← filsDroit(x);

14. àGauche ← faux();

16. jusqu'à estSentinelle(x)

18. si àGauche

19. y ← changerFilsGauche(y,n);

20. sinon

21. y ← changerFilsDroit(y,n);

23. retourner (T);

Exercice 11 Prouver la correction de insérer.

Exercice 12 Prouver que la complexité en temps dans le pire des cas de insérer est où est la hauteur de l'arbre T.

6-4 - Le problème du successeur

Définition 6 Dans un A.B.R., un nœud o est successeur d'un nœud n si aucun nœud de l'arbre ne possède une clé strictement comprise entre clé(n) et clé(o).

Exemple 15 Dans le cas de l'arbre de la figure 6.1, le nœud de clé 50 a pour père le nœud de clé 100.

Fait 4 Un nœud z a pour successeur y si et seulement si :

- x a un fils droit et y est le nœud de clé minimale dans le sous-arbre droit de x ;

- x n'a pas de fils droit et y est le plus proche ancêtre de x dont le fils gauche est ancêtre de x.

preuve :
La preuve est laissée au lecteur.

La fonction suivante requiert une routine auxiliaire qui calcule le nœud de clé minimale parmi les descendants d'un nœud n, lui y compris. Cette routine est définie par la Figure 6.4.

FIG. 6.4 - Calcul du minimum parmi les descendants

1. fonction minimumDescendants(n:nœud): nœud

3. tantque ?FilsGauche(n) faire

4. n ← filsGauche(n);

6. retourner n;

Conséquence directe du Fait 4, la définition et la correction de l'algorithme qui calcule le successeur d'un nœud (Figure 6.5).

FIG. 6.5 - Calcul du successeur

1. fonction successeur(T:arbre; n : nœud) : nœud

3. si ?FilsDroit(n)

4. retourner minimumDescendants(filsDroit(n));

5. sinon

6. p ← père(n);

8. tantque non(estSentinelle(p)) et n ≠ filsGauche(p)

9. n ← p;

10. p ← père(p);

12. retourner(p);

Exercice 13 Prouver que la complexité dans le pire des cas de successeur est en espace de et en temps de où est la hauteur de l'arbre T.

6-5 - Suppression d'un nœud dans un arbre binaire

Le problème qu'on souhaite résoudre ici est la suppression d'un nœud n dans un arbre binaire de recherche de façon naturellement à conserver un arbre binaire de recherche. Deux premiers cas simples se présentent alors :

1. n n'a aucun fils.
La situation est évidente : on supprime le nœud n ;

2. n possède un seul fils.
La situation est tout aussi évidente : on déclare l'unique fils de n fils du père de n. On réalise l'opération dite de détachement.

Écrivons dès à présent cette fonction détacher (Figure 6.7) qui prend pour argument un arbre binaire T et un nœud x (qui n'est pas une sentinelle) possédant au plus un fils et qui supprime dans l'arbre binaire le nœud x en plaçant son éventuel unique fils comme fils gauche (resp. droit) du père de x si x est fils gauche (resp. droit) de son père. Observons que cette fonction dans le cas où x n'a aucun fils, supprime simplement le nœud x.

Exemple 16 Un exemple de détachement est celui décrit par la Figure 6.6. Le nœud 50 est supprimé, son ancien père (le nœud 40) prend pour nouveau fils droit l'ancien fils gauche du nœud 50 à savoir le nœud 45.

FIG. 6.6 - Détachement du nœud 50

En ce qui concerne le problème de suppression, un troisième cas se distingue :

1. n possède deux fils.
On considère son nœud successeur y. Celui-ci est nécessairement un descendant de n (n possède un fils droit) et donc ne peut pas posséder de fils gauche. Il suffit alors que le père de y prenne pour nouveau fils, le fils droit de y (opération de détachement de y) et que y prenne la place de n pour obtenir un arbre binaire de recherche.

FIG. 6.7 - Algorithme de détachement d'un nœud

1. fonction détacher(T : arbre; x : nœud) : arbre

2. si ?FilsDroit(x)

3. f ← filsDroit(x);

4. sinon

5. f ← filsGauche(x);

7. si estRacine(T,x) alors

8. T ← changerRacine(T,f);

9. sinon

10. p ← père(x);

12. si filsGauche(p)=x

13. p ← changerFilsGauche(p,f);

14. sinon               % on a filsDroit(p)=x

15. p ← changerFilsDroit(p,f);

17. retourner T;

Exemple 17 Un exemple de suppression d'un nœud (le nœud 100) ayant deux fils est celui décrit par la Figure 6.8. Sur cet exemple, nous voyons que le nœud 100 est remplacé par son successeur ( le nœud 110) et que celui-ci est détaché (car n'ayant pas de fils gauche), son ancien père (le nœud 200 prend pour nouveau fils gauche l'ancien fils droit de 110 à savoir le nœud 130).

FIG. 6.8 - Suppression du nœud 100

L'algorithme de suppression est décrit dans la Figure 6.9.

FIG. 6.9 - Algorithme de suppression d'un nœud

1. fonction supprimer(T:arbre; x : nœud): arbre

2. si non(?FilsGauche(x)) OU non(?FilsDroit(x))

3. retourner détacher(T,x);

4. sinon

5. s ← successeur(T,x);

6. x ← changerContenu(x,contenu(s));

7. retourner détacher(T,s);

Remarque

Dans l'algorithme détacher, nous avons autorisé la comparaison de deux nœuds en évaluant l'expression filsGauche(p) = x. Or dans le type abstrait nœud, cette possibilité n'était pas offerte. Deux solutions s'offrent à nous :

1. On enrichit le type abstrait d'une opération permettant de tester l'égalité entre deux nœuds :

égalité

: nœud x nœud

→ booléen

2. On ramène l'égalité de deux nœuds en comparant leur clé (sachant que les clés caractérisent les nœuds). En clair, on remplace expression filsGauche(p) = x par clé(filsGauche(p)) = clé(x).

6-6 - Conclusion

Nous avons vu que la complexité en temps des fonctions insérer, supprimer et recherche est au plus égale à la hauteur de l'arbre.

Cette majoration est une bonne nouvelle, car non seulement il existe des arbres de grande taille n et de hauteur (par exemple des arbres binaires parfaits), mais de plus tous le sont ou presque : on démontre sans trop de difficulté qu'un arbre binaire de recherche construit aléatoirement de taille n est de taille .

Ainsi, « sans malchance », la complexité en temps est .

Ce propos malheureusement n'empêche pas des situations d'infortune. En effet, si l'arbre de recherche est dégénéré c'est-à-dire de hauteur proche de sa taille (par exemple des arbres dans lesquels chaque nœud a très souvent au plus un unique fils), la complexité est .

Il existe de nombreuses techniques qui permettent de maintenir un arbre équilibré c'est-à-dire vérifiant hauteur(T) = log{taille(T)). Les familles d'arbres de recherches équilibrés sont d'arité :

- 2. Les arbres rouges et noirs sont un exemple ;

- 3. Chaque nœud possède au plus trois fils. Les 2,3-arbres sont un exemple.

7 - Chapitre 7 - Les arbres rouges et noirs

Nous présentons dans ce chapitre un ensemble de techniques permettant d'implémenter le type ensemble :

estVide

: ensemble

→ booléen

ensembleVide

:

→ ensemble

choisir

: élément

→ élément

appartient

: élément x ensemble

→ booléen

ajouter

: élément x ensemble

→ ensemble

enlever

: élément x ensemble

→ ensemble

selon une complexité en espace et, en notant n la cardinalité de l'ensemble manipulé, selon une complexité en temps dans le pire des cas égale à :

estVide

:

ensembleVide

:

choisir

:

appartient

:

ajouter

:

enlever

:

Nous avons vu dans le dernier chapitre que la représentation d'un ensemble E à l'aide d'un arbre binaire de recherche T garantissait une complexité en temps égale à pour les trois premières fonctions et égale à pour les trois dernières.

Observant que tout arbre binaire a une hauteur au moins égale à (plus exactement à ), pour obtenir une complexité en , il suffit de manipuler des arbres binaires de recherche T vérifiant

Plusieurs familles de tels arbres existent, celle que nous présentons ici est : les arbres rouges et noirs.

7-1 - Définition

Un arbre rouge et noir est un arbre binaire de recherche tel que :

1. Chaque nœud est colorié ou en rouge ou en noir ;

2. Chaque sentinelle est coloriée en noir ;

3. Si un nœud est rouge, ses deux fils sont noirs ;

4. Chaque chemin de la racine à une feuille contient le même nombre de nœuds noirs.

Fait 5 Tout arbre rouge et noir T vérifie :

En fait nous avons :

preuve :
Pour tout arbre rouge et noir T, notons noir(T) l'arbre (non binaire) obtenu à partir de T en coloriant en noir sa racine (voir Exercice 14) et en rattachant chaque fils d'un nœud rouge à son grand-père nécessairement noir. Il vient :

Tout fils d'un sommet rouge étant noir, il vient :

Clairement, noir(T) est un arbre dont tout chemin de la racine à l'une des feuilles est de longueur constante égale à hauteur(noir(T)) et dont chaque nœud possède au moins deux fils, il en découle :

Ce qui suffit à conclure.

Exercice 14 Démontrer qu'en coloriant en noir la racine d'un arbre rouge et noir, on conserve un arbre rouge et noir.

7-2 - Une opération locale : la rotation

Voici deux opérations qui transforment tout arbre binaire de recherche en un arbre binaire de recherche :

Définition 7 Soit T un arbre rouge et noir. Soit y un nœud dont le fils gauche x n'est pas une sentinelle. Nous notons rotationDroite(T,y) l'arbre obtenu à partir de T en prenant :

1. Pour nouveau père de x l'ancien père de y ;

2. Pour nouveau fils gauche de y l'ancien fils droit de x ;

3. Pour nouveau fils droit de x le nœud y.

Soit x un nœud de T dont le fils droit y n'est pas une sentinelle. Nous notons rotationGauche(T,x) l'arbre obtenu à partir de T en prenant :

1. Pour nouveau père de y l'ancien père de x ;

2. Pour nouveau fils droit de x l'ancien fils gauche de y ;

3. Pour nouveau fils gauche de y le nœud x.

Exercice 15 Écrire un algorithme de complexité en temps réalisant la rotation gauche.

Exercice 16 En reprenant les notations de la définition précédente, démontrer que l'arbre T est égal aux deux arbres :

rotationGauche(rotationDroite(T,y) ,x)
rotationDroite(rotationGauche(T,x),y)

Exercice 17 Démontrer que tout arbre binaire de recherche peut être transformé en une « chaîne droite » en au plus n - 1 rotations. En déduire que tout arbre binaire de recherche peut être transformé en tout autre arbre binaire de recherche possédant les mêmes nœuds en au plus 2·(n - 1) rotations.

7-3 - Insérer un nœud

Le problème d'insertion :

problème RN-insérer
Entrée : un arbre rouge et noir T, un nœud x
Sortie : un arbre rouge et noir U dont l'ensemble des nœuds est celui de T augmenté de x

admet comme solution l'algorithme de la Figure 7.1. Afin de simplifier l'écriture, nous utiliserons une procédure colorationRouge qui permet de colorier en rouge tout sommet (ainsi la notation colorationRouge(n) remplace n ← colorationRouge(n).

De plus, nous utilisons de nouvelles primitives frère, estFilsGauche à signification évidente dont l'écriture est laissée en exercice.

Exercice 18 Écrire les algorithmes frère, estFilsGauche, oncle.

7-3-1 - Correction sommaire

Pour prouver la correction de cet algorithme, il suffit de démontrer l'invariance de la propriété suivante : l'arbre T est un arbre rouge et noir exception faite que le nœud x et son père peuvent être rouges.

En conséquence, à la sortie de boucle tantque, il est assuré que ou x est racine ou que son père est noir. Ainsi, l'arbre T retourné est rouge et noir.

7-3-2 - Complexité

Il est assez immédiat d'observer qu'à chaque passage de boucle, la distance de x à la racine diminue strictement. La hauteur de l'arbre étant initialement , la complexité en temps est .

7-4 - Suppression

Le problème de suppression d'un nœud :

problème RN-supprimer
Entrée : un arbre rouge et noir T, un nœud y appartenant à T
Sortie : un arbre rouge et noir U dont l'ensemble des nœuds est celui de T privé de y

admet comme solution l'algorithme défini par les Figures 7.2 et 7.3.

7-4-1 - Correction très sommaire

Conséquence du fait que la modification de l'arbre n'est réalisée qu'au travers de rotations gauches et droites, l'arbre conserve l'ensemble de nœuds initial et demeure un arbre binaire de recherche tout au long de l'algorithme.

Reste à démontrer que l'arbre retourné est un arbre rouge et noir. Cette preuve est présentée au tableau noir de l'amphithéâtre par utilisation de craies rouges.

7-4-2 - Complexité

Infortunément à chaque passage de boucle, le sommet x ne se rapproche pas de la racine, ainsi dans le cas où son frère est rouge, une conséquence de la rotation est que, dans le nouveau nœud z peut rester à une même distance de la racine que l'ancien nœud z. Cependant, dans ce cas, on est assuré que le nouveau nœud x a un frère noir, ce qui permet par le prochain passage de boucle de se rapprocher strictement de la racine.

Ainsi, après deux passages de boucle consécutifs, la distance de x à la racine décroît strictement. Toutes les instructions de l'algorithme correction étant de complexité en temps , on déduit que correction est de complexité en temps .

On étend naturellement ce résultat à détacher et RN-supprimer.

Exercice 19 Est-ce que pour tout nœud x et pour tout arbre rouge et noir T, l'arbre T est égal à RN-supprimer(RN-insérer(T,x),x) ?

FIG. 7.1 - Insertion dans un arbre rouge et noir

1. fonction RN-insérer(T : RN-arbre; x : nœud) : RN-arbre

2. colorationRouge(x);

3. colorationNoir(racine(T));

4. T ← insérer(T,x);

6. tantque x ≠ racine(T) et couleur(père(x)) = rouge faire

7. si estFilsGauche(père(x)) alors

8. si couleur(oncle(x)) = rouge alors

9. colorationNoir(père(x));

10. colorationNoir(oncle(x));

11. colorationRouge(père(père(x)));

12. x ← père(père(x));

13. sinon

14. si estFilsDroit(x) alors

15. T ← rotationGauche(T,père(x));

16. x ← filsGauche(x);

18. colorationNoir(père(x));

19. colorationRouge(père(père(x)));

20. T ← rotationDroite(T,père(père(x)));

22. sinon    % même instruction en échangeant gauche et droite

23. retourner(T);

FIG. 7.2 - Suppression dans un arbre rouge et noir

1. fonction RN-supprimer(T: RN-arbre; y : nœud) : RN-arbre

3. si ?FilsGauche(y) ET ?FilsDroit(y) alors

4. y ← changerContenu(y,successeur(T,y));

5. y ← successeur(T,y);

6. si ?FilsGauche(y) alors

7. x ← filsGauche(y);

8. sinon

9. x ← filsDroit(y);

11. T ← détacher(T,y);

13. si couleur(y) = rouge alors

14. retourner T;

15. sinon

16. retourner correction(T,x);

FIG. 7.3 - Suppression dans un arbre rouge et noir

1. fonction correction(T: RN-arbre; x : nœud) : RN-arbre

3. tantque x ≠ racine(T) ET couleur(x) = noir faire

4. si estFilsGauche(x) alors

5. w ← frère(x);

7. si couleur(w)=rouge alors

8. colorationNoir(w);

9. colorationRouge(père(x));

10. T ← rotationGauche(T,père(x));

11. w ← frère(x);

13. % on a couleur(w)=noir

15. si couleur(filsGauche(w))=noir ET couleur(filsDroit(w))=noir alors

16. colorationRouge(w);

17. colorationNoir(père(x));

18. x ← père(x);

19. sinon

20. si couleur(filsGauche(w)) = rouge alors

21. colorationNoir(filsGauche(w));

22. colorationRouge(w);

23. T ← rotationDroite(T,w);

24. w ← filsDroit(père(x));

26. % on a couleur(filsGauche(w))=noir

27. %   et couleur(filsDroit(w))=rouge

29. si couleur(père(x)) = noir alors

30. colorationNoir(filsDroit(w));

32. T ← rotationGauche(T,père(x));

33. x ← racine(T);

35. retourner T;

8 - Chapitre 8 - Le type partition

Un objet commun en mathématique est la notion de partition d'un ensemble E. Nous montrons dans ce chapitre commet implémenter efficacement des partitions à l'aide d'arbres et obtenir des instructions de complexité en temps constante !

8-1 - Préalables mathématiques

Une partition d'un ensemble E est un ensemble de parties de E non vides deux à deux disjointes (d'intersection vide) dont l'union forme E.

Rappelons que la notion de partition d'un ensemble est identique à la notion de relation d'équivalence, une relation d'équivalence est une relation réflexive, symétrique et transitive :

1. Toute partition d'un ensemble admet pour relation d'équivalence la relation qui relie deux objets appartenant à une même partie de E :

;

2. Inversement, toute relation d'équivalence sur un ensemble induit comme partition celle composée des classes d'équivalence :

La partition discrète d'un ensemble est la partition composée des singletons .

Nous appellerons union l'opération qui associe à une partition d'un ensemble et à deux éléments non équivalents et la partition obtenue à partir de en réalisant l'union des classes de et .

8-2 - Un type abstrait partition

Suite aux définitions précédentes, nous définissons le type abstrait suivant :

Type Partition

Utilise : booléen, ensemble

Opérations

partitionDiscrete

: ensemble

→ partition

equivalent

: partition x élément x élément

→ booléen

union

: partition x élément x élément

→ partition

8-3 - Quelques premières implémentations

8-3-1 - À l'aide de séquences et de listes chaînées

Une première implémentation consiste à définir chacune des classes à l'aide d'une séquence.

Exemple 18 La partition {{1,4,6},{2,5},{3}} se représente par exemple à l'aide de l'ensemble {(1,6, 4), (2, 5), (3)}.

Décider si deux éléments a et b sont équivalents nécessite alors de tester l'appartenance de a à la séquence contenant b.

Si la séquence est représentée à l'aide d'une liste chaînée, ce test est de complexité en temps linéaire.

8-3-2 - À l'aide d'étoiles (arbres de hauteur 1)

Pour réaliser le test d'équivalence en temps constant, il est nécessaire d'associer pour chaque élément en temps constant un objet qui caractérise la classe à laquelle il appartient.

Une solution est d'associer à chaque élément un élément singulier de sa classe d'équivalence, que nous appellerons son représentant. L'objet ainsi défini peut se définir de façon équivalente comme ;

1. Un objet mathématique : une fonction de dans vérifiant  ;

2. Un objet informatique : un tableau à indices dans à valeurs dans  ;

3. Un objet graphique : une étoile.

Exemple 19 Ainsi, la partition {{1, 4,6}, {2,5}, {3}} se représente par exemple à l'aide du tableau T :

1

2

3

4

5

6

4

2

3

4

5

4

Ainsi tester l'équivalence de deux éléments a et b se fait en temps constant : il suffit de tester l'égalité T[a]=T[b].

Malheureusement, si l'on souhaite réaliser l'union de deux éléments, il est nécessaire pour l'une des deux classes dont on souhaite faire l'union de modifier l'objet caractéristique de cette classe. Cette modification doit concerner chacun des éléments de cette classe. Sa complexité en temps est proportionnelle à la cardinalité de cette classe et est donc linéaire.

8-4 - Implémentation à l'aide d'arbres

Une idée consiste à considérer un objet plus complexe que l'étoile à savoir un arbre : ainsi toute classe est représentée à l'aide d'un arbre dont la racine est le représentant.

Exemple 20 Ainsi, la partition {{1,4,6,8,9,10},{2,5,7},{3}} se représente par exemple à l'aide des trois arbres :

Calculer le représentant d'un élément nécessite alors de calculer la racine de l'arbre auquel il appartient.

Décider si deux éléments sont équivalents revient à calculer puis à comparer leur représentant.

Réaliser l'union de deux éléments revient à calculer leur représentant puis à placer l'un des deux représentants fils de l'autre représentant.

Ainsi, les opérations sur ces arbres ne consistent qu'à « remonter » dans l'arbre afin de calculer la racine ascendante d'un élément courant. Une représentation optimale d'un arbre est de le représenter à l'aide d'un simple tableau indiquant pour chaque élément son père (pour des raisons de simplicité, on considèrera le père de la racine égale à la racine elle-même).

Exemple 21 Ainsi, l'ensemble des trois arbres représentant la partition {{1, 4, 6, 8,9, 10}, {2, 5,7}, {3}}

est représenté à l'aide du tableau :

1

2

3

4

5

6

7

8

9

10

6

2

3

4

2

4

5

4

4

6

8-4-1 - Une première implémentation

Pour des raisons de simplification, nous supposerons que l'univers E forme un intervalle d'entiers de la forme avec . Ainsi, la signature de partitionDiscrete devient :

partitionDiscrete

: entier

→ partition

En implémentant une partition comme une structure contenant pour seul champ un champ de nom père de type tableau, nous obtenons :

1. fonction partitionDiscrete(n : entier) : partition

2. tab ← tableau(n)(1);

4. pour i de 1 à n faire

5. tab[i] ← i

7. p ← structure(pere)(tab);

9. retourner p;

Conformément à la section précédente, nous enrichissons le type abstrait de l'opération :

représentant

: partition x élément

→ élément

qui a pour implémentation :

1. fonction représentant(p:partition; a : élément) :élément

2. si p.pere[a] ≠ a alors

3. retourner représentant(p, p.pere[a])

4. sinon

5. retourner p.pere[a];

7. fonction équivalent(p:partition; a : élément; b : élément): booléen

8. retourner représentant(p,a) = représentant(p,b)

10. fonction union(p:partition; a : élément; b : élément): partition

12. a ← représentant(p, a);

13. b ← représentant(p, b);

15. p.pere[a] ← b;

17. retourner p;

La complexité en temps de union ou équivalent dépend de la complexité de représentant qui est exactement la profondeur dans l'arbre de l'élément a, à savoir la distance de celui-ci à la racine qui peut être égale à la taille de l'arbre.

Exercice 20 Dessiner la partition retournée par l'algorithme suivant. Démontrer que le programme suivant a une complexité en temps égale à .

1. fonction test(n:entier) : partition

2. p ← partitionDiscrete(n);

4. pour i de 2 à n faire

5. p ← union(p,1,i);

7. retourner p;

Exercice 21 Dessiner la partition retournée par l'algorithme suivant. Démontrer que le programme suivant a une complexité en temps égale à .

1. fonction test(n:entier) : partition

2. p ← partitionDiscrete(n);

4. pour i de 2 à n faire

5. p ← union(p,i-1,i);

7. retourner p;

8-4-2 - Une seconde implémentation

Une première idée : transformation dynamique de l'arbre

Afin de diminuer ces complexités en temps, une première idée consiste chaque fois que l'on calcule le représentant r d'un élément a de profiter de ce calcul pour modifier l'arbre de façon à ce que le prochain calcul soit plus rapide. Dans notre cas, il suffit d'écraser l'arbre en faisant de a et de tous ses ascendants des fils de r.

Exemple 22 Ainsi, le calcul du représentant de l'élément 11 dans l'arbre de gauche modifiera l'arbre à gauche de la Figure 8.1 en l'arbre dessiné à droite :

FIG. 8.1 - Un arbre écrasé dynamiquement

L'algorithme permettant de calculer le représentant d'un élément est défini sur la Figure 8.2. Il nécessite une fonction auxiliaire permettant de calculer l'ensemble des nœuds ascendants d'un nœud donné (algorithme de la Figure 8.3).

FIG. 8.2 - Calcul du représentant

1. fonction représentant2(p:partition; a : élément) :élément x partition

2. ascendants ← calculAscendants(p, a);

4. (r,ascendants) ← extraire(ascendants);

6. tantque est(nonVide(ascendants)) faire

7. (b,ascendants) + extraire(ascendants);

8. p.pere[b] + r;

10. retourner (r,p);

Une seconde idée : minimisation des hauteurs.

Afin d'obtenir des arbres de hauteur minimale, on enrichit la partition d'une information sur chacun des éléments appelée son poids, mesurant en fait l'importance du nœud racine. Ce poids n'est modifié que lorsqu'une racine admet pour nouveau fils un élément de même poids.

Les algorithmes deviennent :

FIG. 8.3 - Calcul des ascendants

1. fonction partitionDiscrete2(n : entier) : partition

3. tab ← tableau(n)(1);

4. poids ← tableau(n)(0);

6. pour i de 1 à n faire

7. tab[i] ← i

9. p ← structure(pere,poids)(tab,poids);

10. retourner p;

12. fonction calculAscendants(p:partition; a : élément) : pile

14. ascendants ← empiler(a,pileVide());

16. tantque a ≠ p.pere[a] faire

17. a ← p.pere[a];

18. ascendants ← empiler(a,ascendants);

20. retourner ascendants;

1. fonction union2(p:partition; a : élément; b : élément): partition

3. (a,p) ← representant2(p , a);

4. (b,p) ← representant2(p , b);

6. si p.poids[a] > p.poids[b] alors

7. p.pere[b] ← a;

8. sinon

9. p.pere[al ← b;

11. si p.poids[al=p.poids [b] alors

12. p.poids[b] ← p.poids[b]+1;

14. retourner p;

8-4-3 - Calcul des complexités

Complexité logarithmique

Il est aisé d'observer qu'un élément a fils d'un élément b a un poids strictement inférieur. Ainsi, la hauteur d'un arbre n'excède pas le poids de sa racine.

On peut démontrer que tout arbre dont la racine est de poids p possède au moins 2p éléments.

Conséquence de ces deux observations, la complexité en temps dans le pire des cas de union2, représentant2 ainsi que equiv est .

Exercice 22 Démontrer que tout arbre dont la racine est de poids p possède au moins 2p éléments.

Complexité amortie (quasi) constante

En réalité, nous avons un résultat de complexité bien plus intéressant. Pour cela nous ne considérons pas la complexité dans le pire des cas de chaque exécution d'une des fonctions, mais nous considérons un programme globalement. Considérons un programme lors duquel est créée une partition de n éléments et lors duquel sont exécutées m instructions union2, représentant2 ou equiv.

Il est alors possible de prouver (une preuve est disponible dans le chapitre 22 du Cormen) que le coût total de ces m instructions est , ce qui ramène le coût (amorti) de chaque instruction à un coût (quasi) constant (voir la définition de ci-dessous).

Présentation succincte de

Une définition précise de est disponible dans le Cormen. Disons simplement que est une fonction croissante qui associe à tout entier de la forme son nombre de niveaux. Nous avons : , , , , , etc.

En conséquence de quoi, un entier pour lequel est au moins égal à et est donc bien supérieur au nombre d'atomes présents dans l'univers observable (évalué à ).

Ainsi, d'un point de vue pratique, doit être considéré comme constant : nous ne manipulerons jamais une partition de cardinalité supérieure à .

8-5 - Utilisation de partition

Le premier ascendant commun de deux nœuds dans un arbre est ascendant commun de plus grande profondeur. On considère ici qu'un nœud est ascendant de lui-même.

Si nous souhaitons calculer le premier ascendant commun à deux nœuds, il est nécessaire de remonter (éventuellement totalement) les deux chemins allant de ces deux nœuds en direction de la racine. La complexité est alors au moins la différence de la profondeur de cet ascendant avec celle du nœud le plus profond. Dans le pire des cas, cette complexité peut être la hauteur de l'arbre et donc la taille de l'arbre.

Le problème auquel nous nous intéressons est de calculer dans un arbre pour un ensemble de couples C le premier ascendant commun de chacun des couples. Si nous utilisons une méthode naïve qui consisterait, pour chacun des couples à calculer le premier ascendant commun, nous obtiendrons un algorithme en .

L'algorithme présenté ici est de complexité en temps optimale, car linéaire (égal à où est le nombre de sommets de l'arbre et le nombre de couples de C).

Exemple 23 Ainsi, si T est l'arbre dessiné ci-dessous :

et si C est l'ensemble ((4, 7), (5, 1), (10, 9), (8, 10)), nous souhaitons calculer l'ensemble des triplets :

1. ((4, 7, 2), (5, 1, 2), (4, 9, 2), (10, 9, 8), (8, 10, 8)).

L'algorithme consiste en un parcours en profondeur de l'arbre selon un traitement postfixe. L'ensemble des nœuds traités sont coloriés en noir. Traiter un nœud u consiste à traiter ses fils, puis à calculer l'ascendant de u avec chacun des nœuds noirs souhaités. Afin de simplifier les notations, les variables couleur, ascendant, partition, solution sont considérées comme globales. L'algorithme est le suivant et est défini récursivement à l'aide de la fonction parcours (Figure 8.4).

1. fonction premierAscendant(T:arbre; C : ensemble de couples) : ensemble

3. n ← taille(T);

4. partition ← partitionDiscrete(n);

6. ascendant ← tableau(n)(0);

8. pour i de 1 à n faire

9. couleur ← tableau(n)(blanc);

11. solution ← ensembleVide();

12. premierAscendantRec(racine(T));

14. retourner solution;

La définition de premierAscendantRec colorie des sommets en gris ; cette coloration n'est pas utilisée à l'exécution de l'algorithme (le seul test réalisé est de tester si un sommet est noir). Cet ajout permet une meilleure compréhension de l'algorithme : lors de l'étude la correction de l'algorithme, nous verrons que ces sommets gris forment un chemin de la racine au sommet couramment parcouru.

FIG. 8.4 - Calcul du premier ascendant

1. procédure premierAscendantRec(u : nœud)

3. couleur[u] ← gris;

5. pour chaque fils v de u dans T faire

6. premierAscendantRec(v);

7. partition ← union(partition,u,v);

8. ascendant[representant[u]] ← u

10. pour chaque nœud w tel que {u,w} ∈ C et couleur[w]=noir faire

11. solution ← ajouter(solution, (u,w,ascendant[representant(w)]);

12. couleur[u] ← noir;

Correction

La correction de cet algorithme est la conséquence de l'invariance des propriétés suivantes :

1. Si un nœud est gris, son père est gris ;

2. Si un nœud est noir, son père est ou gris ou noir ;

3. Un nœud est noir si tous ses fils le sont ;

4. Un nœud admet au plus un fils gris ;

5. Les nœuds gris forment un chemin dont l'une des extrémités est la racine et dont la seconde est le nœud u parcouru ;

6. Pour tout nœud noir w, le nœud ascendant[representant(w)] est un ascendant de w qui est gris, mais dont le fils qui est ascendant de w est noir.

Conséquence de ces propriétés, tout premier ascendant commun d'un nœud noir w et d'un nœud gris u est un nœud gris. Puisque le nœud u considéré dans l'algorithme est le prochain nœud colorié en noir, tout sommet gris est ascendant de u. Ainsi, le nœud gris ascendant[representant(w)] est un ascendant commun à u et w et est le premier puisque son unique fils qui est ascendant de w est noir et ne peut donc ainsi être un ascendant de u.

Complexité

Notons n le nombre de nœuds de l'arbre et m la cardinalité de l'ensemble des couples C.

Si l'on suppose que la complexité globale de toutes les exécutions de de l'instruction pour chaque nœud w tel que {u,w}… est égale à (voir exercice), toutes les instructions liées aux appels de fonction union, representant, couleur, ascendant sont de complexité en temps constant. Le nombre d'appels récursifs de la fonction parcours est . La complexité en temps est donc . L'algorithme est donc linéaire.

Exercice 23 En choisissant une structure appropriée pour représenter l'ensemble C, faites en sorte que la complexité globale de toutes les exécutions de de l'instruction pour chaque nœud w tel que {u,w}… soit .

9 - Remerciements

Nous tenons à remercier Claude LELOUP pour la relecture orthographique.