Třídění stromů - Tree sort

Třídění stromů
Třídění binárního stromu (2) .png
Třída Algoritmus řazení
Datová struktura Pole
Nejhorší výkon O ( n ²) (nevyvážený) O ( n log n ) (vyvážený)
Nejlepší výkon O ( n log n )
Průměrný výkon O ( n log n )
Nejhorší prostorová složitost Θ ( n )

Strom druh je řadicí algoritmus , který buduje binární vyhledávací strom z prvků, které mají být tříděny, a pak prochází strom ( in-pořadí ) tak, aby tyto prvky vyjít v seřazeném pořadí. Jeho typickým použitím je třídění prvků online : po každém vložení je sada dosud viděných prvků k dispozici v seřazeném pořadí.

Třídění stromu lze použít jako jednorázové třídění, ale je ekvivalentní s quicksortem, protože oba rekurzivně rozdělují prvky na základě pivot, a protože quicksort je na místě a má nižší režii, má oproti quicksortu několik výhod. Při použití samovyvažovacího stromu má lepší složitost nejhoršího případu, ale ještě větší režii.

Účinnost

Přidání jedné položky do binárního vyhledávacího stromu je v průměru procesem O (log n ) (ve velké notaci O ). Přidání n položek je proces O ( n log n ) , takže třídění stromů je procesem „rychlého třídění“. Přidání položky do nevyváženého binárního stromu vyžaduje v nejhorším případě čas O ( n ) : Když se strom podobá propojenému seznamu ( degenerovaný strom ). To má za následek nejhorší případ O ( n ²) času pro tento třídicí algoritmus. K tomuto nejhoršímu případu dochází, když algoritmus pracuje s již seřazenou sadou nebo s téměř seřazenou, obrácenou nebo téměř obrácenou množinou. Očekávaného času O ( n log n ) však lze dosáhnout zamícháním pole, ale to nepomůže pro stejné položky.

Chování v nejhorším případě lze zlepšit pomocí samovyvažovacího binárního vyhledávacího stromu . Použitím takového stromu má algoritmus nejhorší výkon O ( n log n ) , což je pro srovnávací řazení optimální . Algoritmy pro třídění stromů však vyžadují, aby byla pro strom přidělena samostatná paměť, na rozdíl od místních algoritmů, jako je quicksort nebo heapsort . Na většině běžných platforem to znamená, že je třeba použít haldy paměti , což je ve srovnání s quicksortem a heapsortem významný hit výkonu . Při použití stromu splay jako binárního vyhledávacího stromu má výsledný algoritmus (nazývaný splaysort ) další vlastnost, že se jedná o adaptivní řazení , což znamená, že jeho doba běhu je u vstupů, které jsou téměř seřazeny, rychlejší než O ( n log n ) .

Příklad

Následující algoritmus třídění stromů v pseudokódu přijímá kolekci srovnatelných položek a vydává položky ve vzestupném pořadí: 

 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)

V jednoduché funkční programovací formě by algoritmus (v Haskellu ) vypadal asi takto: 

 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

Ve výše uvedené implementaci má algoritmus vložení i algoritmus načítání nejhorší scénáře O ( n ²) .

externí odkazy