Voir la source de Tri arborescent

{{Infobox Algorithme
 | temps max             = <math>O(n^2)</math> non équilibré <math>O(n\log(n))</math> équilibré
}}
Le '''tri arborescent''' est un [[algorithme de tri]] par comparaison, c'est en partie un [[tri par file de priorité]] qui utilise la structure d'[[arbre binaire de recherche]] comme file de priorité. Il est équivalent au [[tri rapide]], en particulier, sa complexité moyenne est [[Notation O|Θ]](''n'' log ''n'') en moyenne mais Θ(n{{2}}) dans le pire cas<ref>{{Ouvrage|langue=en|auteur1=Keith MacLuckie|auteur2=Angus Barber|titre=Sorting routines for microcomputers|éditeur=[[Macmillan Publishers]]|collection=Macmillan microcomputer books|année=1986|isbn=978-0-333-39587-5|consulté le=25 juin 2024}}</ref>. {{refnec|Cependant, il est moins efficace car il nécessite de construire une [[structure de données]] complexe alors que le tri rapide est un [[Algorithme de tri#Tri en place|tri en place]]. Il n'est donc pas utilisé en pratique|date=septembre 2024}}.

== Exemple ==
{{Section rédaction à revoir|date=août 2024}}
Soit à classer par ordre alphabétique ou numérique une série d'éléments (nombres ou mots).

Par exemple, on voudrait classer les termes ''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 :

{{Arbre|contenu=
* camion
** bateau
*** avion
** moto
*** 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é ==
{{refnec|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 <math>n \log n</math>, ce qui est [[Algorithme de tri#Complexité algorithmique|optimal]] pour un tri par comparaison|date=septembre 2024}}.

{{comment|Une variante consiste à utiliser un [[arbre équilibré]]|date=25 juin 2024}}. La [[complexité en temps|complexité]] de l'algorithme est alors <math>\Theta(n \log n)</math> dans tous les cas.

== Notes et références ==
{{Références}}

== Voir aussi ==
=== Articles connexes ===
* [[Tri par tas]]

=== Bibliographie ===
* {{Ouvrage|langue=en|auteur1=Donald Ervin Knuth|titre=The Art of Computer Programming|volume=3|titre volume=Sorting and searching|éditeur=Addison-Wesley|année=1998|mois=janvier|numéro édition=2|pages totales=780|passage=141-144|isbn=978-0-201-89685-5|numéro chapitre=5.2.3|titre chapitre=Sorting by Selection}}

{{Palette|Algorithmes de tri}}
{{Portail|Informatique théorique}}

[[Catégorie:Algorithme de tri|Arborescent]]