Précédent Remonter Suivant

Chapitre 8  Ranger l'information ... pour la retrouver

L'informatique permet de traiter des quantités gigantesques d'information et déjà, on dispose d'une capacité de stockage suffisante pour archiver tous les livres écrits. Reste à ranger cette information de façon efficace pour pouvoir y accéder facilement. On a vu comment construire des blocs de données, d'abord en utilisant des tableaux, puis des objets. C'est le premier pas dans le stockage. Nous allons voir dans ce chapitre quelques-unes des techniques utilisables pour aller plus loin. D'autres manières de faire seront présentées dans le cours INF 421.

8.1  Recherche en table

Pour illustrer notre propos, nous considérerons deux exemples principaux: la correction d'orthographe (un mot est-il dans le dictionnaire ?) et celui de l'annuaire (récupérer une information concernant un abonné).

8.1.1  Recherche linéaire

La manière la plus simple de ranger une grande quantité d'information est de la mettre dans un tableau, qu'on aura à parcourir à chaque fois que l'on cherche une information.

Considérons le petit dictionnaire contenu dans la variable dico du programme ci-dessous:
class Dico{

    static boolean estDans(String[] dico, String mot){
        boolean estdans = false;

        for(int i = 0; i < dico.length; i++)
            if(mot.compareTo(dico[i]) == 0)
                estdans = true;
        return estdans;
    }

    public static void main(String[] args){
        String[] dico = {"maison", "bonjour", "moto",
                         "voiture", "artichaut", "Palaiseau"};

        if(estDans(dico, mot))
            System.out.println("Le mot est présent");
        else
            System.out.println("Le mot n'est pas présent");
    }
}

Pour savoir si un mot est dedans, on le passe sur la ligne de commande par
  unix% java Dico bonjour
On parcourt tout le tableau et on teste si le mot donné, ici pris dans la variable args[0] se trouve dans le tableau ou non. Le nombre de comparaisons de chaînes est ici égal au nombre d'éléments de la table, soit n, d'où le nom de recherche linéaire.

Si le mot est dans le dictionnaire, il est inutile de continuer à comparer avec les autres chaînes, aussi peut-on arrêter la recherche à l'aide de l'instruction break, qui permet de sortir de la boucle for. Cela revient à écrire:
        for(int i = 0; i < dico.length; i++)
            if(mot.compareTo(dico[i]) == 0){
                estdans = true;
                break;
            }

Si le mot n'est pas présent, le nombre d'opérations restera le même, soit O(n).

8.1.2  Recherche dichotomique

Dans le cas où on dispose d'un ordre sur les données, on peut faire mieux, en réorganisant l'information suivant cet ordre, c'est-à-dire en triant, sujet qui formera la section suivante. Supposant avoir trié le dictionnaire, on peut maintenant y chercher un mot par dichotomie, en adaptant le programme déjà donné au chapitre 7, et que l'on trouvera à la figure 8.1. Rappelons que l'instruction x.compareTo(y) sur deux chaînes x et y retourne 0 en cas d'égalité, un nombre négatif si x est avant y dans l'ordre alphabétique et un nombre positif sinon. Comme déjà démontré, le coût de la recherche dans le cas le pire passe maintenant à O(logn).

class Dico{

    // recherche de mot dans dico[g..d[
    static boolean dichoRec(String[] dico, String mot,
                            int g, int d){
        int m, cmp;

        if(g >= d) // l'intervalle est vide
            return false;
        m = (g+d)/2;
        cmp = mot.compareTo(dico[m]);
        if(cmp == 0)
            return true;
        else if(cmp < 0)
            return dichoRec(dico, mot, g, m);
        else
            return dichoRec(dico, mot, m+1, d);
    }

    static boolean estDansDico(String[] dico, String mot){
        return dichoRec(dico, mot, 0, dico.length);
    }

    public static void main(String[] args){
        String[] dico = {"Palaiseau", "artichaut",
                         "bonjour", "maison",
                         "moto", "voiture"};

        for(int i = 0; i < args.length; i++){
            System.out.print("Le mot '"+args[i]);
            if(estDansDico(dico, args[i]))
                System.out.print("' est");
            else
                System.out.println("' n'est pas");
            System.out.println(" dans le dictionnaire");
        }
    }
}

Figure 8.1 : Le programme complet de recherche dichotomique.


Le passage de O(n) à O(logn) peut paraître anodin. Il l'est d'ailleurs sur un dictionnaire aussi petit. Avec un vrai dictionnaire, tout change. Par exemple, le dictionnaire de P. Zimmermann contient 260688 mots de la langue française. Une recherche d'un mot ne coûte que 18 comparaisons au pire dans ce dictionnaire.

8.1.3  Utilisation d'index

On peut repérer dans le dictionnaire les zones où on change de lettre initiale; on peut donc construire un index, codé dans le tableau ind tel que tous les mots commençant par une lettre donnée sont entre ind[i] et ind[i+1]-1. Dans l'exemple du dictionnaire de P. Zimmermann, on trouve par exemple que le mot a est le premier mot du dictionnaire, les mots commençant par b se présentent à partir de la position 19962 et ainsi de suite.

Quand on cherche un mot dans le dictionnaire, on peut faire une dichotomie sur la première lettre, puis une dichotomie ordinaire entre ind[i] et ind[i+1]-1.

8.2  Trier

Nous avons montré l'intérêt de trier l'information pour pouvoir retrouver rapidement ce que l'on cherche. Nous allons donner dans cette section quelques algorithmes de tri des données. Nous ne serons pas exhaustifs sur le sujet, voir par exemple [Knu73] pour plus d'informations.

Deux grandes classes d'algorithmes existent pour trier un tableau de taille n. Ceux dont le temps de calcul est O(n2) et ceux de temps O(n logn). Nous présenterons quelques exemples de chaque. On montrera en INF 421 que O(nlogn) est la meilleure complexité possible pour la classe des algorithmes de tri procédant par comparaison.

Pour simplifier la présentation, nous trierons un tableau de n entiers t par ordre croissant.

8.2.1  Tris élémentaires

Nous présentons ici deux tris possibles, le tri sélection et le tri par insertion. Nous renvoyons à la littérature pour d'autres algorithmes, comme le tri bulle par exemple.

Le tri sélection

Le premier tri que nous allons présenter est le tri par sélection. Ce tri va opérer en place, ce qui veut dire que le tableau t va être remplacé par son contenu trié. Le tri consiste à chercher le plus petit élément de t[0..n[, soit t[m]. À la fin du calcul, cette valeur devra occuper la case 0 de t. D'où l'idée de permuter la valeur de t[0] et de t[m] et il ne reste plus ensuite qu'à trier le tableau t[1..n[. On procède ensuite de la même façon.

L'esquisse du programme est la suivante:
    static void triSelection(int[] t){
        int n = t.length, m, tmp;

        for(int i = 0; i < n; i++){
            // invariant: t[0..i[ contient les i plus petits
            //            éléments du tableau de départ
            m = indice du minimum de t[i..n[
            // on échange t[i] et t[m]
            tmp = t[i]; t[i] = t[m]; t[m] = tmp;
        }
    }
On peut remarquer qu'il suffit d'arrêter la boucle à i = n-2 au lieu de n-1, puisque le tableau t[n-1..n[ sera automatiquement trié.

Notons le rôle du commentaire de la boucle for qui permet d'indiquer une sorte de propriété de récurrence toujours satisfaite au moment où le programme repasse par cet endroit pour chaque valeur de l'indice de boucle.

Reste à écrire le morceau qui cherche l'indice du minimum de t[i..n[, qui n'est qu'une adaptation d'un algorithme de recherche du minimum global d'un tableau. Finalement, on obtient la fonction suivante:
    static void triSelection(int[] t){
        int n = t.length, m, tmp;

        for(int i = 0; i < n-1; i++){
            // invariant: t[0..i[ contient les i plus petits
            //            éléments du tableau de départ
            // recherche de l'indice du minimum de t[i..n[
            m = i;
            for(int j = i+1; j < n; j++)
                if(t[j] < t[m])
                    m = j;
            // on échange t[i] et t[m]
            tmp = t[i]; t[i] = t[m]; t[m] = tmp;
        }
    }
qu'on utilise par exemple dans:
    public static void main(String[] args){
        int[] t = {3, 5, 7, 3, 4, 6};

        triSelection(t);
    }

Analysons maintenant le nombre de comparaisons faites dans l'algorithme. Pour chaque valeur de i ∈ [0, n-2], on effectue n-1-i comparaisons à l'instruction if(t[j] < t[m]), soit au total:
(n-1)+(n-2)+⋯+1 = n(n-1)/2
comparaisons. L'algorithme fait donc O(n2) comparaisons. De même, on peut compter le nombre d'échanges. Il y en a 3 par itération, soit 3 (n-1) = O(n).

Le tri par insertion

Ce tri est celui du joueur de cartes qui veut trier son jeu (c'est une idée farfelue, mais pourquoi pas). On prend en main sa première carte (t[0]), puis on considère la deuxième (t[1]) et on la met devant ou derrière la première, en fonction de sa valeur. Après avoir classé ainsi les i-1 premières cartes, on cherche la place de la i-ième, on décale alors les cartes pour insérer la nouvelle carte.

Regardons sur l'exemple précédent, la première valeur se place sans difficulté:
3          
On doit maintenant insérer le 5, ce qui donne:
3 5        
puisque 5 > 3. De même pour le 7. Arrive le 3. On doit donc décaler les valeurs 5 et 7
3   5 7    
puis insérer le nouveau 3:
3 3 5 7    
Et finalement, on obtient:
3 3 4 5 6 7
Écrivons maintenant le programme correspondant. La première version est la suivante:
    static void triInsertion(int[] t){
        int n = t.length, j, tmp;

        for(int i = 1; i < n; i++){
            // t[0..i-1] est déjà trié
            j = i;
            // recherche la place de t[i] dans t[0..i-1]
            while((j > 0) && (t[j-1] > t[i]))
                j--;
            // si j = 0, alors t[i] <= t[0]
            // si j > 0, alors t[j] > t[i] >= t[j-1]
            // dans tous les cas, on pousse t[j..i-1]
            // vers la droite
            tmp = t[i];
            for(int k = i; k > j; k--)
                t[k] = t[k-1];
            t[j] = tmp;
        }
    }
La boucle while doit être écrite avec soin. On fait décroître l'indice j de façon à trouver la place de t[i]. Si t[i] est plus petit que tous les éléments rencontrés jusqu'alors, alors le test sur j-1 serait fatal, j devant prendre la valeur 0. À la fin de la boucle, les assertions écrites sont correctes et il ne reste plus qu'à déplacer les éléments du tableau vers la droite. Ainsi les éléments précédemment rangés dans t[j..i-1] vont se retrouver dans t[j+1..i] libérant ainsi la place pour la valeur de t[i]. Il faut bien programmer en faisant décroître k, en recopiant les valeurs dans l'ordre. Si l'on n'a pas pris la précaution de garder la bonne valeur de t[i] sous le coude (on dit qu'on l'a écrasée), alors le résultat sera faux.

Dans cette première fonction, on a cherché d'abord la place de t[i], puis on a tout décalé après-coup. On peut condenser ces deux phases comme ceci:
    static void triInsertion(int[] t){
        int n = t.length, j, tmp;

        for(int i = 1; i < n; i++){
            // t[0..i-1] est déjà trié
            tmp = t[i];
            j = i;
            // recherche la place de tmp dans t[0..i-1]
            while((j > 0) && (t[j-1] > tmp)){
                t[j] = t[j-1]; j = j-1;
            }
            // ici, j = 0 ou bien tmp >= t[j-1]
            t[j] = tmp;
        }
    }
On peut se convaincre aisément que ce tri dépend assez fortement de l'ordre initial du tableau t. Ainsi, si t est déjà trié, ou presque trié, alors on trouve tout de suite que t[i] est à sa place, et le nombre de comparaisons sera donc faible. On montre qu'en moyenne, l'algorithme nécessite un nombre de comparaisons moyen égal à n (n+3)/4-1, et un cas le pire en (n-1)(n+2)/2. C'est donc encore un algorithme en O(n2), mais avec un meilleur cas moyen.

Exercice. Pour quelle permutation le maximum de comparaisons est-il atteint? Montrer que le nombre moyen de comparaisons de l'algorithme a bien la valeur annoncée ci-dessus.

8.2.2  Un tri rapide: le tri par fusion

Il existe plusieurs algorithmes dont la complexité atteint O(n log n) opérations, avec des constantes et des propriétés différentes. Nous avons choisi ici de présenter uniquement le tri par fusion.

Ce tri est assez simple à imaginer et il est un exemple classique de diviser pour résoudre. Pour trier un tableau, on le coupe en deux, on trie chacune des deux moitiés, puis on interclasse les deux tableaux. On peut déjà écrire simplement la fonction implantant cet algorithme:
    static int[] triFusion(int[] t){
        if(t.length == 1) return t;
        int m = t.length / 2;
        int[] tg = sousTableau(t, 0, m);
        int[] td = sousTableau(t, m, t.length);

        // on trie les deux moitiés
        tg = triFusion(tg);
        td = triFusion(td);
        // on fusionne
        return fusionner(tg, td);
    }
en y ajoutant la fonction qui fabrique un sous-tableau à partir d'un tableau:
    // on crée un tableau contenant t[g..d[
    static int[] sousTableau(int[] t, int g, int d){
        int[] s = new int[d-g];

        for(int i = g; i < d; i++)
            s[i-g] = t[i];
        return s;
    }

On commence par le cas de base, c'est-à-dire un tableau de longueur 1, donc déjà trié. Sinon, on trie les deux tableaux t[0..m[ et t[m..n[ puis on doit recoller les deux morceaux. Dans l'approche suivie ici, on retourne un tableau contenant les éléments du tableau de départ, mais dans le bon ordre. Cette approche est couteuse en allocation mémoire, mais suffit pour la présentation. Nous laissons en exercice le codage de cet algorithme par effets de bord.

Il nous reste à expliquer comment on fusionne deux tableaux triés dans l'ordre. Reprenons l'exemple du tableau:
    int[] t = {3, 5, 7, 3, 4, 6};
Dans ce cas, la moitié gauche triée du tableau est tg = {3, 5, 7}, la moitié droite est td = {3, 4, 6}. Pour reconstruire le tableau fusionné, noté f, on commence par comparer les deux valeurs initiales de tg et td. Ici elles sont égales, on décide de mettre en tête de f le premier élément de tg. On peut imaginer deux pointeurs, l'un qui pointe sur la case courante de tg, l'autre sur la case courante de td. Au départ, on a donc:

À la deuxième étape, on a déplacé les deux pointeurs, ce qui donne:

Pour programmer cette fusion, on va utiliser deux indices g et d qui vont parcourir les deux tableaux tg et td. On doit également vérifier que l'on ne sort pas des tableaux. Cela conduit au code suivant:
    static int[] fusionner(int[] tg, int[] td){
        int[] f = new int[tg.length + td.length];
        int g = 0, d = 0;

        for(int k = 0; k < f.length; k++){
            // f[k] est la case à remplir
            if(g >= tg.length) // g est invalide
                f[k] = td[d++];
            else if(d >= td.length) // d est invalide
                f[k] = tg[g++];
            else // g et d sont valides
                if(tg[g] <= td[d])
                    f[k] = tg[g++];
                else // tg[g] > td[d]
                    f[k] = td[d++];
        }
        return f;
    }
Le code est rendu compact par utilisation systématique des opérateurs de post-incrémentation. Le nombre de comparaisons dans la fusion de deux tableaux de taille n est O(n).

Appelons T(n) le nombre de comparaisons de l'algorithme complet. On a:



qui se résout en écrivant:



Si n = 2k, alors T(2k) = 2 k 2k = O(n logn) et le résultat reste vrai pour n qui n'est pas une puissance de 2. C'est le coût, quelle que soit le tableau t.

Que reste-t-il à dire? Tout d'abord, la place mémoire nécessaire est 2 n, car on ne sait pas fusionner en place deux tableaux. Il existe d'autres tris rapides, comme heapsort et quicksort, qui travaillent en place, et ont une complexité moyenne en O(nlogn), avec des constantes souvent meilleures.

D'autre part, il existe une version non récursive de l'algorithme de tri par fusion qui consiste à trier d'abord des paires d'éléments, puis des quadruplets, etc. Nous laissons cela à titre d'exercice.

8.3  Stockage d'informations reliées entre elles

Pour l'instant, nous avons vu comment stocker des informations de même type, mais sans lien entre elles. Voyons maintenant quelques exemples où existent de tels liens.

8.3.1  Piles

Nous avons déjà croisé les piles dans le chapite 4. Les informations sont stockées dans l'ordre de leur arrivée. Le premier élément arrivé se trouve dans le fond. Le dernier arrivé peut sortir, ainsi qu'il est montré dans le dessin qui suit:

Nous pouvons définir la classe Pile en représentant celle-ci par un tableau dont la taille sera créée à la construction:
class Pile{
    int hauteur;
    int[] t;

    static Pile creer(int taille){
        Pile p = new Pile();

        p.t = new int[taille];
        p.hauteur = -1;
        return p;
    }
}
Par convention, la pile vide sera caractérisée par une hauteur égale à -1. Si la hauteur est positive, c'est l'indice où le dernier élément arrivé a été stocké. On teste que la pile est vide par:
    static boolean estVide(Pile p){
        return p.hauteur == -1;
    }
On peut alors empiler ou dépiler des informations:
    static void empiler(Pile p, int x){
        p.hauteur += 1;
        p.t[p.hauteur] = x;
    }

    static int depiler(Pile p){
        return p.t[p.hauteur--];
    }
Un programme de test pourra être:
class TesterPile{
    public static void main(String[] args){
        Pile p = Pile.creer(10);
        int x;

        Pile.empiler(p, 1);
        Pile.empiler(p, 2);
        x = Pile.depiler(p);
        System.out.println(x);
    }
}

8.3.2  Files d'attente

Le premier exemple est celui d'une file d'attente à la poste. Là, je dois attendre au guichet, et au départ, je suis à la fin de la file, qui avance progressivement vers le guichet. Je suis derrière un autre client, et il est possible qu'un autre client entre, auquel cas il se met derrière moi. La façon la plus simple de gérer la file d'attente est de la mettre dans un tableau t de taille TMAX, et de mimer les déplacements vers les guichets. Quelles opérations pouvons-nous faire sur ce tableau ? On veut ajouter un client entrant à la fin du tableau, et servir le prochain client, qu'on enlève alors du tableau. Le postier travaille jusqu'au moment où la file est vide.

Examinons une façon d'implanter une file d'attente, ici rangée dans la classe Queue. On commence par définir:
class Queue{
    int fin;
    int[] t;

    static Queue creer(int taille){
        Queue q = new Queue();

        q.t = new int[taille];
        q.fin = 0;
        return q;
    }
}
La variable fin sert ici à repérer l'endroit du tableau t où on stockera le prochain client. Il s'ensuit que la fonction qui teste si une queue est vide est simplement:
    static boolean estVide(Queue q){
        return q.fin == 0;
    }
L'ajout d'un nouveau client se fait simplement: si le tableau n'est pas rempli, on le met dans la case indiquée par fin, puis on incrémente celui-ci:
    static boolean ajouter(Queue q, int i){
        if(q.fin >= q.t.length)
            return false;
        q.t[q.fin] = i;
        q.fin += 1;
        return true;
    }
Quand on veut servir un nouveau client, on teste si la file est vide, et si ce n'est pas le cas, on sort le client suivant de la file, puis on décale tous les clients dans la file:
    static void servirClient(Queue q){
        if(!estVide(q)){
            System.out.println("Je sers le client "+q.t[0]);
            for(int i = 1; i < q.fin; i++)
                q.t[i-1] = q.t[i];
            q.fin -= 1;
        }
    }
Un programme d'essai pourra être:
class Poste{
    static final int TMAX = 100;

    public static void main(String[] args){
        Queue q = Queue.creer(TMAX);

        Queue.ajouter(q, 1);
        Queue.ajouter(q, 2);
        Queue.servirClient(q);
        Queue.servirClient(q);
        Queue.servirClient(q);
    }
}
On peut améliorer la classe Queue de sorte à ne pas avoir à décaler tous les clients dans le tableau, mais en gérant également un indice debut qui marque la position du prochain client à servir. On peut alors pousser à une gestion circulaire du tableau, pour le remplir moins vite. Nous laissons ces deux optimisations en exercice.

Dans cet exemple, on a relié l'information de façon implicite par la place qu'elle occupe par rapport à sa voisine.

8.3.3  Information hiérarchique

Arbre généalogique

Étant donnée une personne p, elle a deux parents (une mère et un père), qui ont eux-mêmes deux parents. On aimerait pouvoir stocker facilement un tel arbre. Une solution possible est de ranger tout cela dans un tableau a[1..TMAX] (pour les calculs qui suivent, il est plus facile de stocker les éléments à partir de 1 que de 0), de telle sorte que a[1] (au niveau 0) soit la personne initiale, a[2] son père, a[3] sa mère, formant le niveau 1. On continue de proche en proche, en décidant que a[i] aura pour père a[2*i], pour mère a[2*i+1], et pour enfant (si i > 1) la case a[i/2]. Illustrons notre propos par un dessin, construit grâce aux bases de données utilisées dans le logiciel GeneWeb réalisé par Daniel de Rauglaudre1. On remarquera qu'en informatique, on a tendance à dessiner les arbres la racine en haut.



Parmi les propriétés supplémentaires, nous aurons que si i>1, alors une personne stockée en a[i] avec i impair sera une mère, et un père quand i est pair. On remarque qu'au niveau ℓ≥ 0, on a exactement 2 personnes présentes; le niveau ℓ est stocké entre les indices 2 et 2ℓ+1-1.

Tas, file de priorité

La structure de données que nous venons de définir est en fait très générale. On dit qu'un tableau t[0..TMAX] possède la propriété de tas si pour tout i>0, t[i] (un parent2) est plus grand que ses deux enfants gauche t[2*i] et droit t[2*i+1].

Le tableau t = {0, 9, 8, 2, 6, 7, 1, 0, 3, 5, 4} (rappelons que t[0] ne nous sert à rien ici) a la propriété de tas, ce que l'on vérifie à l'aide du dessin suivant:


Figure 8.2 : Exemple de tas.


Bien que nous puissions nous contenter d'utiliser un tableau ordinaire, il est plus intéressant d'utiliser une classe spéciale, que nous appelerons Tas, et qui nous permettra de ranger les éléments de façon dynamique en gérant un indice n, qui désignera le nombre d'éléments présents dans le tas:
class Tas{
    int[] t; // la partie utile est t[1..tmax]
    int n; // indice du dernier élément

    static Tas creer(int tmax){
        Tas tas = new Tas();

        tas.t = new int[tmax+1];
        tas.n = 0;
        return tas;
    }
}

La première fonction que l'on peut utiliser est celle qui teste si un tas a bien la propriété qu'on attend:
    static boolean estTas(Tas tas){
        for(int i = tas.n; i > 1; i--)
            if(tas.t[i] > tas.t[i/2])
                return false;
        return true;
    }

Proposition 4   Soit n≥ 1 et t un tas. On définit la hauteur du tas (ou de l'arbre) comme l'entier h tel que 2hn < 2h+1. Alors

(i) L'arbre a h+1 niveaux, l'élément t[1] se trouvant au niveau 0.

(ii) Chaque niveau, 0 ≤ ℓ < h, est stocké dans t[2
..2ℓ+1[ et comporte ainsi 2 éléments. Le dernier niveau (ℓ=h) contient les éléments t[2h..n].

(iii) Le plus grand élément se trouve en
t[1].

Exercice. Écrire une fonction qui à l'entier in associe son niveau dans l'arbre.

On se sert d'un tas pour implanter facilement une file de priorité, qui permet de gérer des clients qui arrivent, mais avec des priorités qui sont différentes, contrairement au cas de la poste. À tout moment, on sait qui on doit servir, le client t[1]. Il reste à décrire comment on réorganise le tas de sorte qu'à l'instant suivant, le client de plus haute priorité se retrouve en t[1]. On utilise de telles structures pour gérer les impressions en Unix, ou encore dans l'ordonnanceur du système.

Dans la pratique, le tas se comporte comme un lieu de stockage dynamique où entrent et sortent des éléments. Pour simuler ces mouvements, on peut partir d'un tas déjà formé t[1..n] et insérer un nouvel élément x. S'il reste de la place, on le met temporairement dans la case d'indice n+1. Il faut vérifier que la propriété est encore satisfaite, à savoir que le père de t[n+1] est bien supérieur à son fils. Si ce n'est pas le cas, on les permute tous les deux. On n'a pas d'autre test à faire, car au cas où t[n+1] aurait eu un frère, on savait déjà qu'il était inférieur à son père. Ayant permuté père et fils, il se peut que la propriété de tas ne soit toujours pas vérifiée, ce qui fait que l'on doit remonter vers l'ancestre du tas éventuellement.

Illustrons tout cela sur un exemple, celui de la création d'un tas à partir du tableau:
    int[] a = {6, 4, 1, 3, 9, 2, 0, 5, 7, 8};
Le premier tas est facile:



L'élément 4 vient naturellement se mettre en position comme fils gauche de 6:



et après insertion de 1 et 3, on obtient:



Ces éléments sont stockés dans le tableau
i 1 2 3 4
t[i] 6 4 1 3
Pour s'en rappeler, on balaie l'arbre de haut en bas et de gauche à droite.

On doit maintenant insérer 9, ce qui dans un premier temps nous donne



On voit que 9 est plus grand que son père 4, donc on les permute:



Ce faisant, on voit que 9 est encore plus grand que son père, donc on le permute, et cette fois, la propriété de tas est bien satisfaite:



Après insertion de tous les éléments de t, on retrouve le dessin de la figure 8.2.

Le programme Java d'insertion est le suivant:
    static boolean inserer(Tas tas, int x){
        if(tas.n >= tas.t.length)
            // il n'y a plus de place
            return false;
        // il y a encore au moins une place
        tas.n += 1;
        tas.t[tas.n] = x;
        monter(tas, tas.n);
        return true;
    }

et utilise la fonction de remontée:
    // on vérifie que la propriété de tas est vérifiée
    // à partir de tas.t[k]
    static void monter(Tas tas, int k){
        int v = tas.t[k];

        while((k > 1) && (tas.t[k/2] <= v)){
            // on est à un niveau > 0 et 
            // le père est <= fils
            // le père prend la place du fils
            tas.t[k] = tas.t[k/2];
            k /= 2;
        }
        // on a trouvé la place de v
        tas.t[k] = v;
    }
Pour transformer un tableau en tas, on utilise alors:
    static Tas deTableau(int[] a){
        Tas tas = creer(a.length);

        for(int i = 0; i < a.length; i++)
            inserer(tas, a[i]);
        return tas;
    }

Pour parachever notre travail, il nous faut expliquer comment servir un client. Cela revient à retirer le contenu de la case t[1]. Par quoi la remplacer ? Le plus simple est de mettre dans cette case t[n] et de vérifier que le tableau présente encore la propriété de tas. On doit donc descendre dans l'arbre.

Reprenons l'exemple précédent. On doit servir le premier client de numéro 9, ce qui conduit à mettre au sommet le nombre 4:



On doit maintenant faire descendre 4:



ce qui conduit à l'échanger avec son fils gauche:



puis on l'échange avec 7 pour obtenir finalement:



La fonction de ``service'' est:
    static void servirClient(Tas tas){
        if(tas.n > 0){
            System.out.println("Je sers le client "+tas.t[1]);
            tas.t[1] = tas.t[tas.n];
            tas.n -= 1;
            descendre(tas, 1);
        }
    }
qui appelle:
    static void descendre(Tas tas, int k){
        int v = tas.t[k], j;

        while(k <= tas.n/2){
            // k a au moins 1 fils gauche
            j = 2*k;
            if(j < tas.n)
                // k a un fils droit
                if(tas.t[j] < tas.t[j+1])
                    j++;
            // ici, tas.t[j] est le plus grand des fils
            if(v >= tas.t[j])
                break;
            else{
                // on échange père et fils
                tas.t[k] = tas.t[j];
                k = j;
            }
        }
        // on a trouvé la place de v
        tas.t[k] = v;
    }
Notons qu'il faut gérer avec soin le problème de l'éventuel fils droit manquant. De même, on n'échange pas vraiment les cases, mais on met à jour les cases pères nécessaires.
Proposition 5   La complexité des procédures monter et descendre est O(h) ou encore O(log2 n).

Démonstration: on parcourt au plus tous les niveaux de l'arbre à chaque fois, ce qui fait au plus O(h) mouvements.



Pour terminer cette section, nous donnons comme dernier exemple d'application un nouveau tri rapide, appelé tri par tas (en anglais, heapsort). L'idée est la suivante: quand on veut trier le tableau t, on peut le mettre sous la forme d'un tas, à l'aide de la procédure deTableau déjà donnée. Celle-ci aura un coût O(n h), puisqu'on doit insérer n éléments avec un coût O(h). Cela étant fait, on permute le plus grand élément t[1] avec t[n], puis on réorganise le tas t[1..n-1], avec un coût O(log2(n-1)). Finalement, le coût de l'algorithme sera O(n h) = O(nlog2 n). Ce tri est assez séduisant, car son coût moyen est égal à son coût le pire: il n'y a pas de tableaux difficiles à trier. La procédure Java correspondante est:
    static void triParTas(int[] a){
        Tas tas = deTableau(a);

        for(int k = tas.n; k > 1; k--){
            // a[k..n[ est déjà trié, on trie a[0..k-1]
            // t[1] contient max t[1..k] = max a[0..k-1]
            a[k-1] = tas.t[1];
            tas.t[1] = tas.t[k];
            tas.n -= 1;
            descendre(tas, 1);
        }
        a[0] = tas.t[1];
    }

8.4  Conclusions

Nous venons de voir comment stocker des informations présentant des liens entre elles. Ce n'est qu'une partie de l'histoire. Dans les bases de données, on stocke des informations pouvant avoir des liens compliqués entre elles. Pensez à une carte des villes de France et des routes entre elles, par exemple. Des structures de données plus complexes seront décrites dans les autres cours (graphes) qui permettront de résoudre des problèmes plus complexes: comment aller de Paris à Toulouse en le moins de temps possible, etc.




1
http://cristal.inria.fr/~ddr/GeneWeb/
2
Notez le renversement de la propriété généalogique

Précédent Remonter Suivant