Sortering med ett binärt träd
Sortering med hjälp av ett binärt träd (binär trädsortering, trädsortering, trädsortering, sortering med binärt träd, eng. tree sort ) är en universell sorteringsalgoritm som består i att bygga ett binärt sökträd med hjälp av nycklarna till en array (lista), följt av sammansättning av den resulterande matrisen genom att korsa noderna i det konstruerade trädet i önskad ordning av nycklarna. Denna sort är optimal när du tar emot data genom att direkt läsa från en ström (till exempel en fil, socket eller konsol).
Algoritm
- Konstruktion av ett binärt träd.
- Sammansättning av den resulterande arrayen genom att korsa noderna i önskad ordning av nycklarna.
Effektivitet
Proceduren för att lägga till ett objekt till ett binärt träd har en genomsnittlig algoritmisk komplexitet av ordningen . Följaktligen kommer komplexiteten för n objekt att vara , vilket klassificerar sortering med hjälp av ett binärt träd som en grupp av "snabba sorteringar". Komplexiteten för att lägga till ett objekt i ett obalanserat träd kan dock vara så hög som , vilket kan leda till en övergripande komplexitet av storleksordningen .
När du fysiskt expanderar en trädstruktur i minnet krävs åtminstone ytterligare minnesceller (varje nod måste innehålla referenser till ett element i den ursprungliga arrayen, till det överordnade elementet, till vänster och höger blad), men det finns sätt att minska det extra minne som krävs.
Implementeringsexempel
I en enkel form av funktionell programmering i Haskell skulle den här algoritmen se ut så här:
dataträd a = Blad | _ Nod ( Träd a ) a ( Träd a )
infoga :: Ord a => a -> Träd a -> Träd a
insert x Leaf = Nod Leaf x Leaf
insert x ( Node t y t' ) | x <= y = Nod ( infoga x t ) y t'
infoga x ( Nod t y t' ) | x > y = Nod t y ( infoga x t' )
platta :: Träd a -> [ a ]
platta Löv = []
platta ( Node t x t' ) = platta t ++ [ x ] ++ platta t'
trädort :: Ord a => [ a ] -> [ a ]
trädort = platta . foldr infoga Blad
Implementering i C++14 :
#inkludera <minne>
#include <cassert>
#inkludera <algoritm>
#inkludera <vektor>
#include <iostream>
använder namnutrymme std ;
// klass som representerar en binär
trädklass BinaryTree
{
skyddad :
// binär
trädnodstruktur BinaryTreeNode
{
shared_ptr < BinaryTreeNode > vänster , höger ; // vänster och höger underträd int nyckel ; // nyckel };
shared_ptr < BinaryTreeNode > m_root ; // trädrotsskyddad :
// procedur för rekursiv nyckelinsättning
// cur_node - den aktuella noden i trädet som den infogade noden jämförs med // node_to_insert - den infogade noden void insert_recursive ( const shared_ptr < BinaryTreeNode >& cur_node , const shared_tree_No Binary > & Tree_No )
{
hävda ( cur_node != nullptr );
// jämför
bool insertIsLess = node_to_insert -> nyckel < cur_node -> nyckel ;
if ( insertIsLess )
{
// infoga i vänstra underträdet
if ( cur_node -> left == nullptr )
cur_node -> left = node_to_insert ;
annan
infoga_rekursiv ( cur_node -> left , node_to_insert );
}
annan
{
// infoga i höger underträd
if ( cur_node -> höger == nullptr )
cur_node -> höger = nod_to_insert ;
annan
infoga_rekursiv ( cur_node -> höger , nod_to_insert );
}
}
offentliga :
void insert ( int nyckel )
{
shared_ptr < BinaryTreeNode > node_to_insert ( ny BinaryTreeNode );
node_to_insert -> nyckel = nyckel ;
if ( m_root == nullptr )
{
m_root = nod_to_insert ;
återvända ;
}
infoga_rekursiv ( m_root , nod_to_insert );
}
offentliga :
typedef funktion < void ( int nyckel ) > Besökare ;
skyddad :
// rekursiv trädgenomgångsprocedur
// cur_node - för närvarande besökt nod void visit_recursive ( const shared_ptr < BinaryTreeNode >& cur_node , const Besökare & besökare )
{
hävda ( cur_node != nullptr );
// besök först det vänstra underträdet
if ( cur_node -> left != nullptr )
besök_rekursiv ( cur_node -> vänster , besökare );
// besök den aktuella elementbesökaren
(cur_node - > nyckel ) ;
// besök höger underträd
if ( cur_node -> right != nullptr )
besök_rekursiv ( cur_node -> höger , besökare );
}
offentliga :
ogiltigt besök ( const Besökare & besökare )
{
if ( m_root == nullptr )
återvända ;
besök_rekursiv ( m_root , besökare );
}
};
int main ()
{
BinaryTree ; _
// lägga till element i
trädvektorn < int > data_to_sort = { 10 , 2 , 7 , 3 , 14 , 7 , 32 };
for ( int värde : data_to_sort )
{
träd . infoga ( värde );
}
// trädgenomgångsträd . besök ([]( int visited_key )
{
cout << visited_key << " " ;
});
cout << endl ;
// exekveringsresultat: 2 3 7 7 10 14 32
return 0 ;
}
Ett exempel på att skapa ett binärt träd och sortera i Java :
// Kompilera och skriv java TreeSort
class Tree {
public Tree left ; // vänster och höger underträd och nyckel
offentligt träd höger ;
offentlig intkey ; _
public Tree ( int k ) { // konstruktor med
nyckelinitieringsnyckel = k ;
}
/* insert (lägger till ett nytt underträd (nyckel))
jämför nyckeln för underträdet som ska läggas till (K) med nyckeln för rotnoden (X).
Om K>=X, lägg rekursivt till ett nytt träd till det högra underträdet.
Om K<X, lägg rekursivt till ett nytt träd till det vänstra underträdet.
Om det inte finns något underträd, infoga ett nytt träd på denna plats
*/
public void insert ( Tree aTree ) {
if ( aTree . key < key )
if ( left != null ) left . infoga ( aTree );
annat vänster = aTree ;
annat
om ( rätt != null ) rätt . infoga ( aTree );
annat rätt = aTree ;
}
/* traversera
Rekursivt genom det vänstra underträdet.
Använd funktionen f (print) på rotnoden.
Traversera det högra underträdet rekursivt.
*/
public void travers ( TreeVisitor- besökare ) {
if ( left != null )
left . traversera ( besökare );
besökare . besök ( detta );
om ( höger != null )
rätt . traversera ( besökare );
}
}
gränssnitt TreeVisitor {
public void visit ( trädnod ) ;
};
class KeyPrinter implementerar TreeVisitor {
public void visit ( Tränod ) { System . _ ut . println ( " " + nod . nyckel ); } };
class TreeSort {
public static void main ( String args [] ) {
Tree myTree ;
myTree = nytt träd ( 7 ); // skapa ett träd (med nyckel)
myTree . infoga ( nytt träd ( 5 ) ); // bifoga underträd
myTree . infoga ( nytt träd ( 9 ) );
mitt träd . traversa ( ny KeyPrinter ());
}
}
Se även