Tri de l'arbre - Tree sort

Tri de l'arbre
Arbre binaire sort(2).png
Classer Algorithme de tri
Structure de données Déployer
Performances dans le pire des cas O ( n ²) (asymétrique) O ( n log n ) (équilibré)
Le meilleur cas la performance O ( n log n )
Performances moyennes O ( n log n )
Complexité spatiale dans le pire des cas ( n )

Un tri par arbre est un algorithme de tri qui construit un arbre de recherche binaire à partir des éléments à trier, puis parcourt l'arbre ( dans l'ordre ) de sorte que les éléments sortent dans l'ordre trié. Son utilisation typique est le tri des éléments en ligne : après chaque insertion, l'ensemble des éléments vus jusqu'à présent est disponible dans l'ordre trié.

Le tri par arborescence peut être utilisé comme tri ponctuel, mais il est équivalent au tri rapide car les deux partitions récursivement les éléments en fonction d'un pivot, et puisque le tri rapide est en place et a moins de frais généraux, il présente peu d'avantages par rapport au tri rapide. Il a une meilleure complexité dans le pire des cas lorsqu'un arbre d'auto-équilibrage est utilisé, mais encore plus de frais généraux.

Efficacité

L'ajout d'un élément à un arbre de recherche binaire est en moyenne un processus O (log n ) (en grande notation O ). L'ajout de n éléments est un processus O ( n log n ) , faisant du tri par arborescence un processus de « tri rapide ». L'ajout d'un élément à un arbre binaire déséquilibré nécessite O ( n ) temps dans le pire des cas : lorsque l'arbre ressemble à une liste chaînée ( arbre dégénéré ). Il en résulte dans le pire des cas de O ( n ²) du temps pour cet algorithme de tri. Ce pire cas se produit lorsque l'algorithme opère sur un ensemble déjà trié, ou presque trié, inversé ou presque inversé. Le temps O ( n log n ) attendu peut cependant être atteint en mélangeant le tableau, mais cela n'aide pas pour des éléments égaux.

Le comportement dans le pire des cas peut être amélioré en utilisant un arbre de recherche binaire à équilibrage automatique . En utilisant un tel arbre, l'algorithme a une performance dans le pire des cas O ( n log n ) , ce qui en fait un degré optimal pour un tri par comparaison . Cependant, les algorithmes de tri d'arborescence nécessitent l'allocation de mémoire séparée pour l'arborescence, contrairement aux algorithmes sur place tels que quicksort ou heapsort . Sur la plupart des plates-formes courantes, cela signifie que la mémoire de tas doit être utilisée, ce qui représente un impact significatif sur les performances par rapport à quicksort et heapsort . Lors de l'utilisation d'un arbre splay comme arbre de recherche binaire, l'algorithme résultant (appelé splaysort ) a la propriété supplémentaire qu'il s'agit d'un tri adaptatif , ce qui signifie que son temps d'exécution est plus rapide que O ( n log n ) pour les entrées qui sont presque triées.

Exemple

L'algorithme de tri arborescent suivant en pseudocode accepte une collection d'éléments comparables et génère les éléments dans l'ordre croissant : 

 STRUCTURE BinaryTree
     BinaryTree:LeftSubTree
     Object:Node
     BinaryTree:RightSubTree
 
 PROCEDURE Insert(BinaryTree:searchTree, Object:item)
     IF searchTree.Node IS NULL THEN
         SET searchTree.Node TO item
     ELSE
         IF item IS LESS THAN searchTree.Node THEN
             Insert(searchTree.LeftSubTree, item)
         ELSE
             Insert(searchTree.RightSubTree, item)
 
 PROCEDURE InOrder(BinaryTree:searchTree)
     IF searchTree.Node IS NULL THEN
         EXIT PROCEDURE
     ELSE
         InOrder(searchTree.LeftSubTree)
         EMIT searchTree.Node
         InOrder(searchTree.RightSubTree)
 
 PROCEDURE TreeSort(Collection:items)
     BinaryTree:searchTree
    
     FOR EACH individualItem IN items
         Insert(searchTree, individualItem)
    
     InOrder(searchTree)

Dans une forme de programmation fonctionnelle simple , l'algorithme (en Haskell ) ressemblerait à ceci : 

 data Tree a = Leaf | Node (Tree a) a (Tree a)

 insert :: Ord a => a -> Tree a -> Tree a
 insert x Leaf = Node Leaf x Leaf
 insert x (Node t y s)
     | x <= y = Node (insert x t) y s
     | x > y  = Node t y (insert x s)

 flatten :: Tree a -> [a]
 flatten Leaf = []
 flatten (Node t x s) = flatten t ++ [x] ++ flatten s

 treesort :: Ord a => [a] -> [a]
 treesort = flatten . foldr insert Leaf

Dans la mise en œuvre ci-dessus, à la fois l'algorithme d'insertion et l'algorithme de récupération ont O ( n ²) des pires scénarios.

Liens externes