Ordinamento dell'albero - Tree sort

Ordinamento dell'albero

Classe	Algoritmo di ordinamento
Struttura dati	Vettore
Prestazioni nel caso peggiore	O ( n ²) (sbilanciato) O ( n log n ) (bilanciato)
Best-caso le prestazioni	O ( n log n )
Prestazioni medie	O ( n log n )
Complessità dello spazio nel caso peggiore	( n )

Un ordinamento ad albero è un algoritmo di ordinamento che costruisce un albero di ricerca binario dagli elementi da ordinare, quindi attraversa l'albero ( in-order ) in modo che gli elementi vengano visualizzati in ordine. Il suo uso tipico è l'ordinamento degli elementi in linea : dopo ogni inserimento, l'insieme degli elementi visti finora è disponibile in ordine ordinato.

L'ordinamento ad albero può essere utilizzato come ordinamento una tantum, ma è equivalente al quicksort poiché entrambi partizionano ricorsivamente gli elementi in base a un pivot e poiché il quicksort è sul posto e ha un sovraccarico inferiore, presenta pochi vantaggi rispetto al quicksort. Ha una complessità migliore nel caso peggiore quando viene utilizzato un albero autobilanciato, ma anche un sovraccarico.

Efficienza

L'aggiunta di un elemento a un albero di ricerca binario è in media un processo O (log n ) (in notazione O grande ). L'aggiunta di n elementi è un processo O ( n log n ) , che rende l'ordinamento ad albero un processo di "ordinamento rapido". L'aggiunta di un elemento a un albero binario non bilanciato richiede tempo O ( n ) nel caso peggiore: quando l'albero assomiglia a una lista concatenata ( albero degenerato ). Ciò si traduce in un caso peggiore di tempo O ( n ²) per questo algoritmo di ordinamento. Questo caso peggiore si verifica quando l'algoritmo opera su un insieme già ordinato, o uno che è quasi ordinato, invertito o quasi invertito. Il tempo O previsto ( n log n ) può comunque essere ottenuto mescolando l'array, ma questo non aiuta per elementi uguali.

Il comportamento nel caso peggiore può essere migliorato utilizzando un albero di ricerca binario autobilanciato . Usando un tale albero, l'algoritmo ha una prestazione nel caso peggiore O ( n log n ) , essendo quindi ottimale per un grado per un ordinamento di confronto . Tuttavia, gli algoritmi di ordinamento ad albero richiedono l'allocazione di memoria separata per l'albero, a differenza degli algoritmi sul posto come quicksort o heapsort . Sulla maggior parte delle piattaforme comuni, ciò significa che deve essere utilizzata la memoria heap , il che rappresenta un notevole calo delle prestazioni rispetto a Quicksort e Heapsort . Quando si utilizza un albero splay come albero di ricerca binario, l'algoritmo risultante (chiamato splaysort ) ha la proprietà aggiuntiva di essere un ordinamento adattivo , il che significa che il suo tempo di esecuzione è più veloce di O ( n log n ) per gli input che sono quasi ordinati.

Esempio

Il seguente algoritmo di ordinamento ad albero in pseudocodice accetta una raccolta di elementi comparabili ed emette gli elementi in ordine crescente:

 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)

In una semplice forma di programmazione funzionale , l'algoritmo (in Haskell ) sarebbe simile a questo:

 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

Nell'implementazione di cui sopra, sia l'algoritmo di inserimento che l'algoritmo di recupero hanno gli scenari peggiori di O ( n ²) .

link esterno

• Binary Tree Java Applet e spiegazione alla Wayback Machine (archiviata il 29 novembre 2016)
• Ordinamento ad albero di un elenco collegato
• Ordinamento ad albero in C++