Tri arborescent

Problème lié	Algorithme de tri
Structures des données	Tableau, arbre binaire

Complexité en temps
Pire cas	$O(n^{2})$
Moyenne	$O(n\log(n))$
Meilleur cas	$O(n\log(n))$

Complexité en espace
Pire cas	$O(n)$

modifier - modifier le code - modifier Wikidata

Le tri arborescent est un algorithme de tri par comparaison qui utilise la structure d'arbre binaire de recherche. Il est équivalent au tri rapide, en particulier, sa complexité moyenne est Θ(n log n) en moyenne mais Θ(n²) dans le pire cas^[1]. Cependant, il est moins efficace car il nécessite de construire une structure de données complexe alors que le tri rapide est un tri en place. Il n'est donc pas utilisé en pratique.^{[réf. nécessaire]}

Exemple

La mise en forme de cette section ne suit pas les recommandations de Wikipédia (juin 2024) : découvrez comment la « wikifier ».

Soit à classer par ordre alphabétique ou numérique une série d'éléments (nombres ou mots), par exemple camion moto voiture bateau train avion fusée.

Une façon très inefficace de les classer serait de comparer chaque élément à tous les autres, ce qui se nomme un tri en N².

Une façon plus rationnelle est de faire usage du fait que lorsqu'une clé est supérieure à une autre, elle est forcément aussi supérieure à toutes celles qui lui étaient inférieures sans qu'il soit besoin de les comparer. C'est le principe même de l'arborescence. Sur des grands ensembles, on peut éviter ainsi quelques dizaines de millions d'opérations qui auraient été inutiles, et ramener un tri de quelques heures à quelques minutes, de quelques minutes à quelques secondes, ou de quelques secondes à un temps qui devient inobservable pour l'utilisateur.

Convenons donc de mettre à gauche d'une clé toutes celles qui lui sont inférieures, et à droite toutes celles qui lui sont supérieures, et ainsi de suite récursivement. Notre arbre des moyens de transport va avoir l'allure suivante :

                        -- camion --
                       |            |
                  -- bateau    --  moto --
                 |             |          |   
               avion         fusée   -- voiture
                                     |
                                   train

Comment afficher maintenant la liste triée que nous cherchions ? En spécifiant l'ordre d'affichage ainsi :

   sub Lister-les-clés (racine)
       si existe sous-arbre-à-gauche alors Lister-les-clés sous-arbre-à-gauche;
       imprimer la clé associée à la racine
       si existe sous-arbre-à-droite alors Lister-les-clés sous-arbre-à-droite;
   fin-sub

On obtient bien :

avion
bateau
camion
fusée
moto
train
voiture

Complexité

On démontre que dans le cas d'une entrée en ordre vraiment aléatoire (en particulier autre chose que celui où toutes les clés sont déjà triées à l'exception de quelques-unes), la complexité moyenne de ce tri est en $n\log n$ , ce qui est optimal pour un tri par comparaison.^{[réf. nécessaire]}

Une variante consiste à utiliser un arbre équilibré^[Comment ?]. La complexité de l'algorithme est alors $\Theta (n\log n)$ dans tous les cas.

Notes et références

↑ (en) Keith MacLuckie et Angus Barber, Sorting routines for microcomputers, Macmillan, coll. « Macmillan microcomputer books », 1986 (ISBN 978-0-333-39587-5)

Voir aussi

Bibliographie

(en) Donald Ervin Knuth, The Art of Computer Programming, vol. 3 : Sorting and searching, Addison-Wesley, janvier 1998, 2^e éd., 780 p. (ISBN 978-0-201-89685-5), chap. 5.2.3 (« Sorting by Selection »), p. 141-144

v · m

Algorithmes de tri

Tris par comparaisons

Sans hypothèse autre

Complexité moyenne ${\mathcal {O}}(n\log n)$	Tri rapide Tri fusion Tri par tas Introsort Smoothsort Timsort Tri arborescent Tri à peigne (?) Tri de Shell (?)
Complexité moyenne ${\mathcal {O}}(n^{2})$	Tri à bulles Tri par insertion Tri par sélection Tri cocktail
Complexité moyenne moins bonne que ${\mathcal {O}}(n^{2})$	Tri spaghetti Tri stupide Tri faire-valoir