Commune · Savoirs
Tri arborescent
Algorithme de tri
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 Θ(n log n) en moyenne mais Θ(n2) dans le pire cas.
Sur Wikipédia
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 Θ(n log n) en moyenne mais Θ(n2) dans le pire cas. 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].
Texte : Wikipédia, CC BY-SA 4.0. · Image : Mathgorges (Public domain) ·
Cartes voisines
-
★★
Arbre binaire de recherche
Structure de données représentant un ensemble ou un tableau associatif
-
★★★
Arbre binaire
Structure de données hiérarchique dans laquelle chaque noeud a au plus 2 fils.
-
★★
Tri par sélection
Algorithme de tri
-
P★
Powersort
Sorting algorithm
-
★★
Tri par insertion
Algorithme de tri
-
T★
Tri comptage
Algorithme de tri