Arbres et tas

I/ Trie

1) Implémentation des arbres binaires

a) Arbres binaires complets

Un arbre binaire est dit complet si tous ses niveaux sont remplis. Autrement dit, toutes ses feuilles sont à la même hauteur.

Voici un arbre binaire complet de hauteur 2 :

Un arbre binaire complet peut être représenté par un tableau, en utilisant le fait que

• La position de chaque enfant gauche est le double de la position de son père.
• La position de chaque enfant droit est le double, incrémenté de 1, de la position de son père.

On introduit un décalage supplémentaire pour tenir compte du fait qu'on compte ) partir de 0 et pas de 1. En C l'arbre binaire ci-dessus peut être représenté ainsi :

char arbre [10];
int i;

int position(char c){
    return c-'a';
} 

char enfant_gauche(char c){
    return arbre[2*position(c)+1];
}

char enfant_droit(char c){
    return arbre[2*position(c)+2];
}

char parent(char c){
    return arbre[(position(c)-1)/2];
}

b) Arbres binaires parfaits

La même représentation peut s'appliquer aussi à un arbre qui n'est pas complet, du moment que

• Seul le dernier niveau n'est pas rempli.
• Les feuilles de ce dernier niveau sont toutes à gauche de l'arbre.

Un tel arbre est dit parfait. Voici un exemple :

Un exemple important d'arbre binaire parfait est le tas (voir plus bas).

2) Trie

Un trie, ou arbre préfixe, est tel que deux mots ont le même père si et seulement s'ils ont le même préfixe :

Dans l'exemple ci-dessus, le trie n'est pas un arbre binaire. Mais on peut le représenter par un arbre binaire.

2) Représentation par un arbre binaire

On convient que

• L'enfant gauche d'un nœud (en rouge) est le premier des enfants de l'arbre d'origine.
• L'enfant droit d'un nœud (en bleu) est l'enfant suivant de son père dans l'arbre d'origine.

La représentation obtenue est plus compacte que celle de l'arbre initial.

3) Algorithme de Liv-Zempel

Un trie peut servir à la compression de fichiers.

L'algorithme de Huffman utilise un arbre préfixe pour coder un texte. Si le codage est binaire, l'arbre l'est aussi. Mais le fichier compressé doit contenir l'arbre ce qui diminue les performances de l'algorithme.

L'algorithme LZW utilise un dictionnaire qui peut être recréé par le décodage.

II/ Arbres bicolores

1) Arbres binaires de recherche

Un arbre binaire de recherche est un arbre binaire (si si !) étiqueté par des éléments d'un ensemble ordonné, et tel que chaque parent a une étiquette

• plus grande que celle de son enfant gauche
• plus petite que celle de son enfant droit.

Les arbres binaires de recherche sont implémentés de façon particulièrement efficace par des arbres rouges-noirs.

2) Arbres rouges-noirs

Un arbre (sous-entendu, binaire) rouge-noir est un arbre binaire colorié en deux couleurs et tel que :

• La racine est noire.
• Les feuilles sont noires.
• Tous les enfants d'un nœud rouge sont noirs.
• Depuis n'importe quelle feuille, on remonte à la racine en rencontrant le même nombre de nœuds noirs.

Ces propriétés optimisent les opérations d'insertion, recherche et suppression.

Voici un exemple d'arbre rouge-noir :

3) Représentation des tableaux associatifs

Les arbres rouges-noirs sont souvent utilisés (en tant qu'arbres binaires de recherche) pour implémenter des tableaux associatifs (struct en C, dict en Python, Object en Javascript, enregistrements en OCaml,...). La recherche d'une clé est rapide si l'arbre binaire de recherche est rouge-noir. Mais la recherche dichotomique nécessite que les clés puissent être ordonnées. La relation d'ordre doit même être totale. C'est le cas pour

• Les clés entières (odre des entiers).
• Les chaînes de caractères (ordre alphabétique).

III/ Tas

1) Définition

Un tas (heap) est un arbre binaire parfait tel que chaque nœud a une valeur (ou « priorité » ) supérieure à celle des ses deux enfants. Cette propriété de tas est récursive.

Voici un exemple de tas :

2) Files de priorité

Une file de priorité est une file dont chaque élément est doté d'une priorité (les priorités sont munies d'un ordre total), et

• Enfiler un élément se fait comme sur une file classique (typiquement à la fin de la file).
• Mais on ne défile pas le premier élément de la file, on défile celui qui a la plus grande priorité.

Un tas permet d'implémenter une file de priorité, de la façon suivante :

• Pour enfiler un élement, on rajoute une feuille comportant cet élément (de telle manière que l'arbre reste parfait) puis on échange éventuellement l'élément avec son père jusqu'à ce que la propriété de tas soit rétablie.
• On défile la racine en la remplaçant par la dernière feuille du tas, puis en échangeant les parents et enfants qui violeraient la propriété de tas.

Les files de priorité sont utilisées notamment (et notoirement) par le noyau Linux pour l'ordonnancement des tâches.

3) Tri par tas (Williams 1964)

a) Algorithme

La structure de tas a été créée pour un algorithme de tri particulièrement efficace. L'idée est de créer un tas à partir de la liste à trier (ce qui est de complexité n×log(n)) puis défiler à chaque étape l'élément de priorité maximale, qui est la racine.

Pour trier la liste [6,3,1,7,5,9,8,2,4] on obtient le tas suivant :

Comme chaque défilement amène à réorganiser le tas pour rétablir la condition de tas, sa complexité dans le pire cas est log(n) donc la complexité des défilements successifs est n×log(n). La complexité du tri par tas est donc optimale : n×log(n).

b) Prim

L'algorithme de Prim pour construire un arbre couvrant de poids minimal utilise une file de priorité. La priorité est le poids des arêtes que l'on garde pour l'arbre couvrant.

c) Dijkstra

L'algorithme de Dijkstra utilise une file de priorité, la priorité étant le coût des arêtes.