Structures arborescentes

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

L'ensemble vide, noté kitxmlcodeinlinelatexdvp\emptysetfinkitxmlcodeinlinelatexdvp, 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.

Le produit cartésien de deux ensembles kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpBfinkitxmlcodeinlinelatexdvp est l'ensemble noté kitxmlcodeinlinelatexdvpA \times Bfinkitxmlcodeinlinelatexdvp ayant pour éléments tous les couples de la forme kitxmlcodeinlinelatexdvp(a, b)finkitxmlcodeinlinelatexdvp avec kitxmlcodeinlinelatexdvpa \in Afinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpb \in Bfinkitxmlcodeinlinelatexdvp.

Une relation binaire kitxmlcodeinlinelatexdvprfinkitxmlcodeinlinelatexdvp définie sur kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpBfinkitxmlcodeinlinelatexdvp est une partie du produit cartésien kitxmlcodeinlinelatexdvpA \times Bfinkitxmlcodeinlinelatexdvp. L'appartenance kitxmlcodeinlinelatexdvp(a, b) \in rfinkitxmlcodeinlinelatexdvp est souvent notée kitxmlcodeinlinelatexdvpa\ r\ bfinkitxmlcodeinlinelatexdvp.

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 kitxmlcodeinlinelatexdvp\mathbb{N}finkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvp\mathbb{N}^*finkitxmlcodeinlinelatexdvp, intervalle d'entiers, relation d'arité kitxmlcodeinlinelatexdvpkfinkitxmlcodeinlinelatexdvp.

Étant donnés deux ensembles kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpBfinkitxmlcodeinlinelatexdvp, une fonction kitxmlcodeinlinelatexdvpffinkitxmlcodeinlinelatexdvp de kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp vers kitxmlcodeinlinelatexdvpBfinkitxmlcodeinlinelatexdvp est une relation binaire kitxmlcodeinlinelatexdvpr \subseteq A \times Bfinkitxmlcodeinlinelatexdvp telle que pour tout élément kitxmlcodeinlinelatexdvpa \in Afinkitxmlcodeinlinelatexdvp il existe un et un seul élément kitxmlcodeinlinelatexdvpb \in Bfinkitxmlcodeinlinelatexdvp tel que kitxmlcodeinlinelatexdvp(a, b) \in ffinkitxmlcodeinlinelatexdvp. L'appartenance kitxmlcodeinlinelatexdvp(a, b) \in ffinkitxmlcodeinlinelatexdvp est notée kitxmlcodeinlinelatexdvpf (a) = bfinkitxmlcodeinlinelatexdvp.

Notions et notations importantes

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

Une séquence à valeurs dans un ensemble kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp est une fonction de la forme kitxmlcodeinlinelatexdvps : \mathbb{N}^* \rightarrow Afinkitxmlcodeinlinelatexdvp ou de la forme kitxmlcodeinlinelatexdvps : [1,i] \rightarrow Afinkitxmlcodeinlinelatexdvp avec kitxmlcodeinlinelatexdvpi \in Nfinkitxmlcodeinlinelatexdvp. Dans ce dernier cas, la séquence kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp peut être notée kitxmlcodeinlinelatexdvp(s(1),\dots , s(i))finkitxmlcodeinlinelatexdvp, l'entier kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp éventuellement nul, est la longueur de kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp.

La séquence vide définie à partir de kitxmlcodeinlinelatexdvp[1,0] = \emptysetfinkitxmlcodeinlinelatexdvp est notée kitxmlcodeinlinelatexdvp()finkitxmlcodeinlinelatexdvp et est de longueur 0.

Notions et notations importantes

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

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⁵ 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 2^5…20 ≃ 10³⁰. 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 kitxmlcodeinlinelatexdvph : \mathcal{A}^* \rightarrow [0, 10^6]finkitxmlcodeinlinelatexdvp 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³⁰ à 10⁶.

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 kitxmlcodeinlinelatexdvpt \ne ufinkitxmlcodeinlinelatexdvp ayant même hachés (kitxmlcodeinlinelatexdvph(t) = h(u)finkitxmlcodeinlinelatexdvp).

Différents choix s'offrent alors.

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.

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 kitxmlcodeinlinelatexdvppfinkitxmlcodeinlinelatexdvp, kitxmlcodeinlinelatexdvpgfinkitxmlcodeinlinelatexdvp, kitxmlcodeinlinelatexdvpdfinkitxmlcodeinlinelatexdvp vérifient respectivement kitxmlcodeinlinelatexdvpg \le p < dfinkitxmlcodeinlinelatexdvp.

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

L'ensemble des opérations

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

Des techniques relativement simples peuvent garantir qu'une hauteur d'arbre raisonnable, voire optimale, à savoir kitxmlcodeinlinelatexdvplog_2(n)finkitxmlcodeinlinelatexdvp où kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp 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 !

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 :

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 :

fonction cardinalité(E:ensemble) :entier
    i ← 0;
    tantque ¬(estVide(E))
        i ← i + 1;
        E ← enlever(choisir(E),E);
    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.

Que signifient les opérations suivantes ?

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 :

fonction union1(A,B:ensemble) :ensemble
    tantque ¬(estVide (B))
        b ← choisir(B);
        B ← enlever(b,B);
        A ← ajouter(b,A);
    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 :

fonction union2(A,B:ensemble) :ensemble
    tantque ¬(estVide(B))
        b ← choisir(B);
        B ← enlever(b,B);
        si ¬(appartient(a,A)) alors
            A ← ajouter(b,A);
    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 :

fonction impairs(A :ensemble) :ensemble
    B ← ensVide();
    tantque ¬(estVide(A)
        a ← choisir(A);
        A ← enlever(a,A);
        si estPair(a) alors
            B ← ajouter(a,B);
    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.

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 kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp.

L'opération ensembliste mathématique sous-jacente est la fonction qui à tout ensemble kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp et à tout élément kitxmlcodeinlinelatexdvpafinkitxmlcodeinlinelatexdvp associe l'ensemble à kitxmlcodeinlinelatexdvpA \cup \{a\}finkitxmlcodeinlinelatexdvp.

Sa définition axiomatique est :

• kitxmlcodeinlinelatexdvp\forall a : element\ \forall b : element\ \forall A : ensemble\qquad appartient(a,ajouter(b,A)) = (a = b) \vee appartient(a,A)finkitxmlcodeinlinelatexdvp

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

L'opération ensembliste mathématique sous-jacente est la fonction qui à tout ensemble kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp et à tout élément kitxmlcodeinlinelatexdvpa \notin Afinkitxmlcodeinlinelatexdvp associe l'ensemble noté kitxmlcodeinlinelatexdvpA \setminus afinkitxmlcodeinlinelatexdvp égal à kitxmlcodeinlinelatexdvpA - \{a\}finkitxmlcodeinlinelatexdvp.

Le mathématicien considèrera que l'expression kitxmlcodeinlinelatexdvp\{a\} \setminus afinkitxmlcodeinlinelatexdvp est incorrecte.

La définition axiomatique de enlever est :

• kitxmlcodeinlinelatexdvp\forall a : element\ \forall b : element\ \forall A : ensemblefinkitxmlcodeinlinelatexdvp

  • kitxmlcodeinlinelatexdvp\lnot(appartient(b,A)) \Rightarrow ( appartient(a,ajouter(b,A)) = (a = b)\ \vee\ appartient(a,A) )finkitxmlcodeinlinelatexdvp

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 :

fonction test(): booléen
    A ← ensembleVide();
    A ← ajouter(1,A);
    A ← ajouter(1,A);
    A ← enlever(1,A);
    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)
• (1,1)
• (1)

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

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 :

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 :

• kitxmlcodeinlinelatexdvp\forall i \in \mathbb{N}\ \forall e : \acute{e}l\acute{e}ment\qquad taille (tableau[i] (e)) = ifinkitxmlcodeinlinelatexdvp
• kitxmlcodeinlinelatexdvp\forall i \in \mathbb{N}\ \forall e : \acute{e}l\acute{e}ment\ \forall j \in [1,i]\qquad lire(tableau[i](e),j) = efinkitxmlcodeinlinelatexdvp
• kitxmlcodeinlinelatexdvp\forall t : tableau\ \forall e : \acute{e}l\acute{e}ment\ \forall j \in [1, taille(t)]\ \forall k \in [1, taille(t)]\setminus j \qquad lire(changer(t,j,e),k) = lire(t,j,e)finkitxmlcodeinlinelatexdvp
• kitxmlcodeinlinelatexdvp\forall t : tableau\ \forall e : \acute{e}l\acute{e}ment\ \forall j \in [1, taille(t)]\qquad lire(changer(t,j,e),j) = efinkitxmlcodeinlinelatexdvp

Exemples

La suite d'instructions suivantes :

t + tableau[5](0);
t[4] ← 10;
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  2   3   4  5
t = (0, 0,  0,  0, 0)
t = (0, 0,  0, 10, 0)
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 i^e é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.

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₁,… , E_n, ainsi qu'un type « identifiant » Id, une définition du type structure peut être :

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

• pour tout entier kitxmlcodeinlinelatexdvpi \in [1,n],\ a \leftarrow s,id_ifinkitxmlcodeinlinelatexdvp se substitue à kitxmlcodeinlinelatexdvpa \leftarrow lire_i(s)finkitxmlcodeinlinelatexdvp ;
• pour tout entier kitxmlcodeinlinelatexdvpi \in [1,n],\ s,id_i \leftarrow afinkitxmlcodeinlinelatexdvp se substitue à kitxmlcodeinlinelatexdvps \leftarrow changer_i(s,a)finkitxmlcodeinlinelatexdvp.

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 )

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 :

Axiomatique

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

• kitxmlcodeinlinelatexdvpestVide(pileVide()) = vrai()finkitxmlcodeinlinelatexdvp
• kitxmlcodeinlinelatexdvp\forall p : pile\ \forall e : \acute{e}l\acute{e}ment\qquad estVide(empiler(p,e)) = fauxfinkitxmlcodeinlinelatexdvp
• kitxmlcodeinlinelatexdvp\forall p : pile\ \forall e : \acute{e}l\acute{e}ment\qquad t\^ete(empiler(p,e)) = efinkitxmlcodeinlinelatexdvp
• kitxmlcodeinlinelatexdvp\forall p : pile\ \forall e : \acute{e}l\acute{e}ment\qquad p = d\acute{e}piler(empiler(p,e))finkitxmlcodeinlinelatexdvp

Exemples

La suite d'instructions suivante :

p ← empiler(pileVide(),10);
a ← tête(p);
p ← empiler(p,20);
b ← tête(p);
p ← empiler(p,30);
c ← tête(p);
p ← dépiler(p);
d ← tête(p);

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

p = (10)         a = 10
p = (20,10)      b = 20
p = (30,20,10)   c = 30
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))

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 :

Axiomatique

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

• kitxmlcodeinlinelatexdvpestVide(fileVide()) = vrai() finkitxmlcodeinlinelatexdvp
• kitxmlcodeinlinelatexdvp\forall e : \acute{e}l\acute{e}ment\qquad 1er\acute{E}l\acute{e}ment(enfiler(fileVide(),e)) = efinkitxmlcodeinlinelatexdvp
• kitxmlcodeinlinelatexdvp\forall e : \acute{e}l\acute{e}ment\qquad estVide(défiler(enfiler(fileVide(),e))) = vrai ()finkitxmlcodeinlinelatexdvp
• kitxmlcodeinlinelatexdvp\forall f : file\ \forall e : \acute{e}l\acute{e}ment\qquad non(estVide(f)) \Rightarrow d\acute{e}filer(enfiler(f,e)) = enfiler(d\acute{e}filer(f),e)finkitxmlcodeinlinelatexdvp
• kitxmlcodeinlinelatexdvp\forall f : file\ \forall e : \acute{e}l\acute{e}ment\qquad estVide(enfiler(f,e)) = faux()finkitxmlcodeinlinelatexdvp

Exemples

La suite d'instructions suivante :

f ← enfiler(fileVide(),10);
a ← 1erÉlément (f);
f ← enfiler(f,20);
b ← 1erÉlément (f);
f ← enfiler(f,30);
c ← 1erÉlément (f);
f ← défiler(f);
d ← 1erÉlément (f);

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

f = (10)         a = 10
f = (10,20)      b = 10
f = (10,20,30)   c = 10
f = (20,30)      d = 20

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 :

Axiomatique

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

• kitxmlcodeinlinelatexdvpestListeVide(listeVide()) = vrai()finkitxmlcodeinlinelatexdvp
• kitxmlcodeinlinelatexdvp\forall l : liste,\ \forall e : \acute{e}l\acute{e}ment,\ \forall i \in \mathbb{N}\\ \quad 1 \le i\le longueur(l)+1 \Rightarrow taille(ins\acute{e}rer(e,i,l)))= taille(l)+1finkitxmlcodeinlinelatexdvp
• kitxmlcodeinlinelatexdvp\forall l : liste, \forall i \in \mathbb{N}\\ \quad 1\le i\le longueur(l) \Rightarrow taille(supprimer(i,l)))= taille(l)-1finkitxmlcodeinlinelatexdvp
• kitxmlcodeinlinelatexdvp\forall l : liste,\ \forall e : \acute{e}l\acute{e}ment,\ \forall (i, j) \in \mathbb{N}^2\\ \quad 1\le j<i\le longueur(l)+1 \Rightarrow i\grave{e}meElmt(ins\acute{e}rer(e,i,l),j) = i\grave{e}meElmt(l, j) \\ \quad 1\le i=j\le longueur(l)+1 \Rightarrow i\grave{e}meElmt(ins\acute{e}rer(e,i,l),j) = e \\ \quad 1\le i<j\le longueur(l)+1 \Rightarrow i\grave{e}meElmt(ins\acute{e}rer(e,i,l),j) = i\grave{e}meElmt(l, j-1)finkitxmlcodeinlinelatexdvp
• kitxmlcodeinlinelatexdvp\forall l : liste,\ \forall (i, j) \in \mathbb{N}² \\ \quad 1\le j\le i\le longueur(l) \Rightarrow i\grave{e}meElmt(supprimer(i,l),j) = i\grave{e}meElmt(l, j) \\ \quad 1\le i\le j\le longueur(l)-1 \Rightarrow i\grave{e}meElmt(supprimer(i,l) ,j) = i\grave{e}meElmt(l, j+1)finkitxmlcodeinlinelatexdvp

Exemples

La suite d'instructions suivante :

l ← insérer(10,1,listeVide());
l ← insérer(20,2,l);
l ← insérer(30,3,l);
l ← insérer(40,2,l);
a ← ièmeElmt(l,1);
b ← ièmeElmt(l,2);
l ← supprimer(3,l);

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

l = (10)
l = (10,20)
l = (10,20,30)
l = (10,40,20,30)
a = 10
b = 40
l = (10,40,30)

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⁸-1], sur 4 octets il s'agit de [0, 2^4·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 kitxmlcodeinlinelatexdvp\simeq \log_2(n)finkitxmlcodeinlinelatexdvp. 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.

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

fonction appartient(e:élément; p : pile) : booléen
    tantque non(estVide(p))
        si tete(p)=e
            retourner vrai();
        p ← dépiler(p);

    retourner faux();

a une complexité en temps kitxmlcodeinlinelatexdvpO(n)finkitxmlcodeinlinelatexdvp (avec n = taille(p)) et en espace kitxmlcodeinlinelatexdvpO(1)finkitxmlcodeinlinelatexdvp. 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

fonction appartient(e:élément; p : pile) : booléen
    tantque non(estVide(p))
        si tete(p)=e
            retourner vrai();
    p ← dépiler(p);

    retourner faux();

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

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 :

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 :

fonction constructNœud(e :élément, n:nœud) :nœud
    retourner structure(cont,suiv)(e,n);

fonction changerSuiv(n:nœud,p:nœud) :nœud
    n.suiv ← p;
    retourner n;

Si l'on souhaite insérer un élément e en i^e 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 :

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

fonction listeVide():liste
    n ← sentinelle();
    n ← changerSuivant(n,sentinelle());
    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 i^e nœud (le nœud sentinelle si i = 0). La fonction ièmeNœud peut ainsi être définie :

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

    pour i ← 1 à i faire
        n ← suivant(n);

    retourner n;

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

fonction ième(l:liste;i:entier) :élément
    retourner contenu(ièmeNœud(l,i));

fonction insérer(l:liste,i:entier,e:élément):liste
    prec ← ièmeNœud(l,i-1);
    n ← constructNœud[e,suivant(prec)](cont, suiv);
    prec ← changerSuiv(prec,n);

    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.

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 :

fonction listeVide() liste
    n ← sentinelle();
    n ← changerSuivant(a,sentinelle());

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

Exercice 5 Écrire les autres primitives du type liste.

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 kitxmlcodeinlinelatexdvpO(longueur(l)^2)finkitxmlcodeinlinelatexdvp, puisque l'exécution de ièmeNœud(l,i) est égale à kitxmlcodeinlinelatexdvpO(i)finkitxmlcodeinlinelatexdvp.

fonction test(l:liste) : liste
    n ← taille(l);

    pour i ← 1 à n
        p ← ièmeNœud(l,i);
        p ← changerCont(p,2·contenu(p));

    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 i^e nœud à chaque appel de la fonction ièmeNœud.

Ainsi, si le curseur est le nœud de rang i (le i^e 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 kitxmlcodeinlinelatexdvpO(i+1)finkitxmlcodeinlinelatexdvp.

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

fonction ièmeNœud(l:liste;i:entier) :nœud
    si l.rangCurseur ≤ i
        n ← n.curseur;
        j ← n.rangCurseur;
    sinon
        n ← l.sentinelleAvant;
        j ← 0;

    tantque j < i faire
        n ← suivant(n);
        j ← j + 1;

    l.curseur ← n;
    l.rangCurseur ← i;
    
    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 à kitxmlcodeinlinelatexdvpO(longueur(l)^2)finkitxmlcodeinlinelatexdvp mais kitxmlcodeinlinelatexdvpO(longueur(l))finkitxmlcodeinlinelatexdvp.

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

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 :

fonction estVide(l : liste) : booléen
    retourner l.longueur = 0;

fonction longueur(l : liste) : entier
    retourner l.longueur;

fonction listeVide() : liste
    n ← sentinelle();
    n ← changerSuivant(a,sentinelle());
    retourner structure(sentinelleAvant,curseur,indiceCurseur, longueur)
                       (n,              n,      0,             0);

fonction ièmeElmt(l : liste; i : entier) : élément
    retourner contenu(ièmeNœud(1, i))

fonction supprimer(l : liste; i : entier) : liste
    n ← ièmeNœud(l,i-1);
    n ← changerSuivant(n,suivant(n));
    retourner l;

fonction insérer(e : élément; i : entier; l : liste ) : liste
    n ← ièmeNœud(l,i-1);
    ajout ← constructNœud(e,suivant(n));
    n ← changerSuiv(n,ajout);

    retourner l;

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 :

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.

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 :

fonction arbreVide() : arbre
    n ← constructSentinelle();
    retourner structure(racine)(n);

fonction estVide(t : arbre) : booléen
    retourner estSentinelle(t.racine);

fonction prendreRacine(n : nœud) : arbre
    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 :

fonction constructNœud(e : élément; g,d,p : nœud ) : nœud
    retourner structure(cont,gauche,droit,père,sent)(e,g,d,p,faux());

fonction constructSentinelle() : nœud
    retourner structure(cont,gauche,droit,père,sent)(0,0,0,0,vrai());

fonction estSentinelle(n : nœud) : booléen
    retourner n.sent;

fonction ?filsGauche(n : nœud) : booléen
    retourner estSentinelle(filsGauche);

fonction changerFilsDroit(n,droit : nœud) : nœud
    n.droit ← droit;
    retourner n;

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 :

traiter1(n1); traiter1(n2); traiter1(n4);
traiter1(n5);
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 :

traiter2(n4);
traiter2(n2);
traiter2(n5);
traiter2(n1);
traiter2(n6);
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 :

traiter3(n4);
traiter3(n5); traiter3(n2);
traiter3(n6);
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 :

fonction parcoursArbre1(T:arbre) : file
    retourner parcours1(racine(T),fileVide());

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

fonction parcoursi(n:nœud,F:file) file
    si non(estSentinelle(n)) alors
        F ← enfiler(contenu(n),F);
        F ← parcoursi(filsGauche(n),F);
        F ← parcoursi(filsDroit(n),F);

    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).

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.

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.

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 kitxmlcodeinlinelatexdvplog(n)finkitxmlcodeinlinelatexdvp, la complexité en temps est kitxmlcodeinlinelatexdvpO(log(n))finkitxmlcodeinlinelatexdvp.

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.

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 kitxmlcodeinlinelatexdvpO(1)finkitxmlcodeinlinelatexdvp, on déduit que correction est de complexité en temps kitxmlcodeinlinelatexdvpO(log(n))finkitxmlcodeinlinelatexdvp.

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) ?

fonction RN-insérer(T : RN-arbre; x : nœud) : RN-arbre
    colorationRouge(x);
    colorationNoir(racine(T));
    T ← insérer(T,x);

    tantque x ≠ racine(T) et couleur(père(x)) = rouge faire
        si estFilsGauche(père(x)) alors
            si couleur(oncle(x)) = rouge alors
                colorationNoir(père(x));
                colorationNoir(oncle(x));
                colorationRouge(père(père(x)));
                x ← père(père(x));
            sinon
                si estFilsDroit(x) alors
                    T ← rotationGauche(T,père(x));
                    x ← filsGauche(x);

                colorationNoir(père(x));
                colorationRouge(père(père(x)));
                T ← rotationDroite(T,père(père(x)));

        sinon    % même instruction en échangeant gauche et droite
    retourner(T);

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

    si ?FilsGauche(y) ET ?FilsDroit(y) alors
        y ← changerContenu(y,successeur(T,y));
        y ← successeur(T,y);
    si ?FilsGauche(y) alors
        x ← filsGauche(y);
    sinon
        x ← filsDroit(y);

    T ← détacher(T,y);

    si couleur(y) = rouge alors
        retourner T;
    sinon
        retourner correction(T,x);

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

    tantque x ≠ racine(T) ET couleur(x) = noir faire
        si estFilsGauche(x) alors
            w ← frère(x);

            si couleur(w)=rouge alors
                colorationNoir(w);
                colorationRouge(père(x));
                T ← rotationGauche(T,père(x));
                w ← frère(x);

                % on a couleur(w)=noir

            si couleur(filsGauche(w))=noir ET couleur(filsDroit(w))=noir alors
                colorationRouge(w);
                colorationNoir(père(x));
                x ← père(x);
            sinon
                si couleur(filsGauche(w)) = rouge alors
                    colorationNoir(filsGauche(w));
                    colorationRouge(w);
                    T ← rotationDroite(T,w);
                    w ← filsDroit(père(x));

                % on a couleur(filsGauche(w))=noir
                %   et couleur(filsDroit(w))=rouge

            si couleur(père(x)) = noir alors
                colorationNoir(filsDroit(w));

            T ← rotationGauche(T,père(x));
            x ← racine(T);

    retourner T;

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.

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 kitxmlcodeinlinelatexdvpffinkitxmlcodeinlinelatexdvp de kitxmlcodeinlinelatexdvpEfinkitxmlcodeinlinelatexdvp dans kitxmlcodeinlinelatexdvpEfinkitxmlcodeinlinelatexdvp vérifiant kitxmlcodeinlinelatexdvpf \circ f = ffinkitxmlcodeinlinelatexdvp ;
2. Un objet informatique : un tableau à indices dans kitxmlcodeinlinelatexdvpEfinkitxmlcodeinlinelatexdvp à valeurs dans kitxmlcodeinlinelatexdvpEfinkitxmlcodeinlinelatexdvp ;
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 :

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.

Pour des raisons de simplification, nous supposerons que l'univers E forme un intervalle d'entiers de la forme kitxmlcodeinlinelatexdvp[1,i]finkitxmlcodeinlinelatexdvp avec kitxmlcodeinlinelatexdvpi \ge 0finkitxmlcodeinlinelatexdvp. Ainsi, la signature de partitionDiscrete devient :

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

fonction partitionDiscrete(n : entier) : partition
    tab ← tableau(n)(1);

    pour i de 1 à n faire
        tab[i] ← i

    p ← structure(pere)(tab);

    retourner p;

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

qui a pour implémentation :

fonction représentant(p:partition; a : élément) :élément
    si p.pere[a] ≠ a alors
        retourner représentant(p, p.pere[a])
    sinon
        retourner p.pere[a];

fonction équivalent(p:partition; a : élément; b : élément): booléen
    retourner représentant(p,a) = représentant(p,b)

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

    a ← représentant(p, a);
    b ← représentant(p, b);

    p.pere[a] ← b;

    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 à kitxmlcodeinlinelatexdvpO(n^2)finkitxmlcodeinlinelatexdvp.

fonction test(n:entier) : partition
    p ← partitionDiscrete(n);

    pour i de 2 à n faire
        p ← union(p,1,i);

    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 à kitxmlcodeinlinelatexdvpO(n)finkitxmlcodeinlinelatexdvp.

fonction test(n:entier) : partition
    p ← partitionDiscrete(n);

    pour i de 2 à n faire
        p ← union(p,i-1,i);

    retourner p;

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 :

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).

fonction représentant2(p:partition; a : élément) :élément x partition
    ascendants ← calculAscendants(p, a);

    (r,ascendants) ← extraire(ascendants);

    tantque est(nonVide(ascendants)) faire
        (b,ascendants) + extraire(ascendants);
        p.pere[b] + r;

    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 :

fonction partitionDiscrete2(n : entier) : partition

    tab ← tableau(n)(1);
    poids ← tableau(n)(0);

    pour i de 1 à n faire
        tab[i] ← i

    p ← structure(pere,poids)(tab,poids);
    retourner p;

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

    ascendants ← empiler(a,pileVide());

    tantque a ≠ p.pere[a] faire
        a ← p.pere[a];
        ascendants ← empiler(a,ascendants);

    retourner ascendants;

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

    (a,p) ← representant2(p , a);
    (b,p) ← representant2(p , b);

    si p.poids[a] > p.poids[b] alors
        p.pere[b] ← a;
    sinon
        p.pere[al ← b;

        si p.poids[al=p.poids [b] alors
            p.poids[b] ← p.poids[b]+1;

    retourner p;

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 2^p é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 kitxmlcodeinlinelatexdvpO(log(n))finkitxmlcodeinlinelatexdvp.

Exercice 22 Démontrer que tout arbre dont la racine est de poids p possède au moins 2^p é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 kitxmlcodeinlinelatexdvpO(m \cdot \log^*(n))finkitxmlcodeinlinelatexdvp, ce qui ramène le coût (amorti) de chaque instruction à un coût (quasi) constant (voir la définition de kitxmlcodeinlinelatexdvplog^*(n)finkitxmlcodeinlinelatexdvp ci-dessous).

Présentation succincte de kitxmlcodeinlinelatexdvplog^*(n)finkitxmlcodeinlinelatexdvp

Une définition précise de kitxmlcodeinlinelatexdvplog^*(n)finkitxmlcodeinlinelatexdvp est disponible dans le Cormen. Disons simplement que kitxmlcodeinlinelatexdvplog^*(n)finkitxmlcodeinlinelatexdvp est une fonction kitxmlcodeinlinelatexdvp\mathbb{N}\rightarrow \mathbb{N}finkitxmlcodeinlinelatexdvp croissante qui associe à tout entier de la forme kitxmlcodeinlinelatexdvp2^{2^{2^{.^{.^{.^{2}}}}}}finkitxmlcodeinlinelatexdvp son nombre de niveaux. Nous avons : kitxmlcodeinlinelatexdvplog^*(2) = 1finkitxmlcodeinlinelatexdvp, kitxmlcodeinlinelatexdvplog^*(2^2) = 2finkitxmlcodeinlinelatexdvp, kitxmlcodeinlinelatexdvplog^*(2^4) = 3finkitxmlcodeinlinelatexdvp, kitxmlcodeinlinelatexdvplog^*(2^{16}) = 4finkitxmlcodeinlinelatexdvp, kitxmlcodeinlinelatexdvplog^*(2^{65536}) = 5finkitxmlcodeinlinelatexdvp, etc.

En conséquence de quoi, un entier kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp pour lequel kitxmlcodeinlinelatexdvplog^*(x) \ge 5finkitxmlcodeinlinelatexdvp est au moins égal à kitxmlcodeinlinelatexdvp2^{65536}finkitxmlcodeinlinelatexdvp et est donc bien supérieur au nombre d'atomes présents dans l'univers observable (évalué à kitxmlcodeinlinelatexdvp10^{80} \simeq 2^{265}finkitxmlcodeinlinelatexdvp).

Ainsi, d'un point de vue pratique, kitxmlcodeinlinelatexdvplog^*(n)finkitxmlcodeinlinelatexdvp doit être considéré comme constant : nous ne manipulerons jamais une partition de cardinalité supérieure à kitxmlcodeinlinelatexdvp2^{65536}finkitxmlcodeinlinelatexdvp.