Worldlex Wiki
Article de reference

Tri par arbre

Le tri arborescent est un algorithme de tri qui construit un arbre binaire de recherche à partir des éléments à trier, puis parcourt cet arbre ( en ordre ) afin que les éléments...

Worldlex WikiContenu en francaisLecture gratuite
algorithme de tri qui construit un arbre binaire de recherche à partir des éléments à trier, puis parcourt cet arbre ( en ordre ) afin que les éléments soient triés. Son utilisation typique est le tri en ligne : après chaque insertion, l’ensemble des éléments déjà traités est disponible trié.

Le tri arborescent peut être utilisé ponctuellement, mais il est équivalent au tri rapide car les deux partitionnent récursivement les éléments à partir d'un pivot. Le tri rapide étant exécuté sur place et ayant une surcharge moindre, le tri arborescent présente peu d'avantages par rapport au tri rapide. Sa complexité dans le pire des cas est meilleure lorsqu'un arbre auto-équilibré est utilisé, mais la surcharge est alors encore plus importante.

notation grand O ). L'ajout de n éléments est un processus liste chaînée ( arbre dégénéré ). Cela se traduit par un temps d'exécution de arbre binaire de recherche auto-équilibré . Avec un tel arbre, l'algorithme atteint une complexité temporelle de tri par comparaison . Cependant, les algorithmes de tri arborescent nécessitent l'allocation de mémoire dédiée à l'arbre, contrairement aux algorithmes en place tels que le tri rapide ou le tri par tas . Sur la plupart des plateformes courantes, cela implique l' utilisation de la mémoire du tas , ce qui représente une perte de performance significative par rapport au tri rapide et au tri par tas . Lorsqu'un arbre splay est utilisé comme arbre binaire de recherche, l'algorithme résultant (appelé tri splay ) possède la propriété supplémentaire d'être un tri adaptatif , ce qui signifie que son temps d'exécution est plus rapide que collection d'éléments comparables et les affiche par ordre croissant :

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

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 " 
données Arbre a = Feuille | Nœud ( Arbre a ) a ( Arbre a )insérer :: Ord a => a -> Arbre a -> Arbre a insérer x Feuille = Noeud Feuille x Feuille insérer x ( Noeud t y s ) | x <= y = Noeud ( insérer x t ) y s | x > y = Noeud t y ( insérer x s )aplatir :: Arbre a -> [ a ] ​​aplatir Feuille = [] aplatir ( Nœud t x s ) = aplatir t ++ [ x ] ++ aplatir stri d'arbres :: Ord a => [ a ] ​​-> [ a ] ​​tri d'arbres = aplatir . insérer une feuille

Dans l'implémentation ci-dessus, l'algorithme d'insertion et l'algorithme de récupération ont tous deux des scénarios de pire cas

Plus d articles de Worldlex Wiki

Revenez a l index pour explorer davantage de pages sur l histoire, la science, la culture, la geographie et la societe en francais.

Explorer l index