78
3 Arbres, algorithmes et données
telle la recherche de motifs : Il permet de chercher un mot u dans le texte w, ou avec
la terminologie que nous avons employée jusqu’ici, un facteur u dans un mot w, en
un temps O(|u|), simplement en examinant le chemin dans le trie correspondant au
mot u. La structure permet de repérer efficacement toutes les répétitions de facteurs,
et peut servir en compression de données. Dans de nombreuses applications une
structure de données quasi équivalente à l’arbre des suffixes est utilisée : il s’agit
de la table des suffixes [52, 126] qui permet d’économiser l’espace mémoire tout
en garantissant de bonnes performances en pratique. Il ne s’agit cependant plus
strictement d’une structure arborescente.
3.3 Tri d’un ensemble de clés
Nous nous intéressons maintenant à des algorithmes permettant de trier un ensemble
de n éléments donnés. Comme dans la section 3.2, chaque élément est composé
d’une clé appartenant à un ensemble totalement ordonné, sur laquelle porte le tri,
et d’autres champs qui ne nous intéressent pas ici. Sauf indication explicite du
contraire (tri radix), nous supposons que la seule opération permise sur les clés,
outre naturellement l’affectation d’une valeur à une variable ou l’échange de deux
clés, est la comparaison de deux clés. En d’autres termes, les clés sont « atomiques »
et nous ne pouvons pas les décomposer.
Dans les algorithmes de tri rapide, de recherche par rang, et de tri par tas, présentés respectivement en sections 3.3.1, 3.3.2 et 3.3.3, les données sont supposées
stockées dans un tableau, mais des arbres sont bien présents ! Ils sont soit implicites,
pour le tri rapide et la recherche par rang où c’est l’exécution de l’algorithme qui
va être mise en lien avec un arbre binaire de recherche, soit explicites pour le tri
par tas, où le tableau sert simplement à implémenter le tas. Quant au tri radix de la
section 3.3.4, il utilise lui aussi un arbre pour représenter les clés, mais cette fois il
s’agit d’un trie, donc d’un arbre digital.
3.3.1 Tri rapide
Algorithme
Le tri rapide (« quicksort » en anglais), dû à Hoare [131], est sans doute le tri le plus
utilisé en pratique ; c’est par exemple le tri standard des systèmes d’exploitation
Unix/Linux et de divers langages de programmation. Il repose sur la structuration
de l’ensemble des clés par rapport à une clé spéciale, utilisée comme pivot. Nous
renvoyons à l’annexe A.6.1 pour l’implémentation du tri rapide, et nous contentons
de donner ci-après son principe général, dont l’algorithme, appelons-le PARTITION,
de partitionnement et placement du pivot est bien entendu une part essentielle
(figure 3.14).
3 Arbres, algorithmes et données
telle la recherche de motifs : Il permet de chercher un mot u dans le texte w, ou avec
la terminologie que nous avons employée jusqu’ici, un facteur u dans un mot w, en
un temps O(|u|), simplement en examinant le chemin dans le trie correspondant au
mot u. La structure permet de repérer efficacement toutes les répétitions de facteurs,
et peut servir en compression de données. Dans de nombreuses applications une
structure de données quasi équivalente à l’arbre des suffixes est utilisée : il s’agit
de la table des suffixes [52, 126] qui permet d’économiser l’espace mémoire tout
en garantissant de bonnes performances en pratique. Il ne s’agit cependant plus
strictement d’une structure arborescente.
3.3 Tri d’un ensemble de clés
Nous nous intéressons maintenant à des algorithmes permettant de trier un ensemble
de n éléments donnés. Comme dans la section 3.2, chaque élément est composé
d’une clé appartenant à un ensemble totalement ordonné, sur laquelle porte le tri,
et d’autres champs qui ne nous intéressent pas ici. Sauf indication explicite du
contraire (tri radix), nous supposons que la seule opération permise sur les clés,
outre naturellement l’affectation d’une valeur à une variable ou l’échange de deux
clés, est la comparaison de deux clés. En d’autres termes, les clés sont « atomiques »
et nous ne pouvons pas les décomposer.
Dans les algorithmes de tri rapide, de recherche par rang, et de tri par tas, présentés respectivement en sections 3.3.1, 3.3.2 et 3.3.3, les données sont supposées
stockées dans un tableau, mais des arbres sont bien présents ! Ils sont soit implicites,
pour le tri rapide et la recherche par rang où c’est l’exécution de l’algorithme qui
va être mise en lien avec un arbre binaire de recherche, soit explicites pour le tri
par tas, où le tableau sert simplement à implémenter le tas. Quant au tri radix de la
section 3.3.4, il utilise lui aussi un arbre pour représenter les clés, mais cette fois il
s’agit d’un trie, donc d’un arbre digital.
3.3.1 Tri rapide
Algorithme
Le tri rapide (« quicksort » en anglais), dû à Hoare [131], est sans doute le tri le plus
utilisé en pratique ; c’est par exemple le tri standard des systèmes d’exploitation
Unix/Linux et de divers langages de programmation. Il repose sur la structuration
de l’ensemble des clés par rapport à une clé spéciale, utilisée comme pivot. Nous
renvoyons à l’annexe A.6.1 pour l’implémentation du tri rapide, et nous contentons
de donner ci-après son principe général, dont l’algorithme, appelons-le PARTITION,
de partitionnement et placement du pivot est bien entendu une part essentielle
(figure 3.14).