imported>Crazy1880: Vorlagen-fix (Datum)

2021-02-27T11:26:22Z

Vorlagen-fix (Datum)

Neue Seite

{{lang|en|'''Binary Tree Sort'''}} ist ein einfacher, in seiner primitivsten Form nicht [[Stabilität (Sortierverfahren)|stabiler]] [[Sortierverfahren|Sortieralgorithmus]].

== Prinzip ==

Bei diesem [[Algorithmus]] werden alle zu sortierenden Elemente nacheinander in einen [[Binärer Suchbaum|binären Suchbaum]] eingefügt. Anschließend wird dieser Baum [[Binärbaum#Traversierung|in-order]] durchlaufen, wobei alle Elemente in sortierter [[Reihenfolge]] angetroffen werden.

In seiner ganz elementaren Form ist der Algorithmus nicht [[Stabilität (Sortierverfahren)|stabil]]. Wird jedoch statt der üblichsten Suchfunktion [[Binärer Suchbaum#Suchen ohne Duplikate (rekursiv)|''Find'']] eine Variante genommen, die auch bei vorhandenem Schlüssel entweder rechts- oder linksseitig immer bis zu den Blättern hinab sucht, wird der Sortieralgorithmus stabil. Dies kann mittels einer [[Binärer Suchbaum#Ordnungsrelation|Vergleichsfunktion]] geschehen, die bei Gleichheit statt dem Rückgabewert 0 immer nur den Wert +1 oder immer nur den Wert −1 zurückgibt (bei gleicher Suchfunktion) resp. einer angepassten Suchfunktion, wie z. B. [[Binärer Suchbaum#Suchen, wenn Duplikate zulässig|''FindDupGE'']].

== Komplexität ==

Die durchschnittliche Komplexität beträgt <math> \mathcal{O}(n \log n) </math>, im [[Zeitkomplexität|Worst Case]] einer bereits sortierten Liste ist sie jedoch <math> \Theta(n^2) </math>. Wird statt des unbalancierten ein [[Balancierter Baum|balancierter binärer Suchbaum]] genommen, ist die Komplexität auch im [[Zeitkomplexität|Worst Case]] <math> \mathcal{O}(n \log n) </math>.

Für den aufzubauenden Suchbaum wird <math> \mathcal{O}(n) </math> zusätzlicher Speicher benötigt.

== Vor- und Nachteile ==

Der Algorithmus wird üblicherweise anhand einer existierenden Implementierung zur [[Verwaltung]] und [[Manipulation]] von [[binärer Baum|binären Bäumen]] implementiert. Auf dieser Grundlage kann er auf zwei einfache Arbeitsschritte – das Anlegen des Baumes und den in-order-Durchlauf – reduziert werden und damit sehr schnell umgesetzt werden.

Gegen ihn spricht die hohe [[Zeitkomplexität]] im Worst Case, der große [[Aufwand]] für die einzelnen [[Operation (Informatik)|Operationen]], der zusätzliche [[Speicherbedarf]] sowie die im Verhältnis zu seiner [[Effizienz (Informatik)|Effizienz]] aufwendige [[Implementierung]], falls diese von Grund auf neu erfolgen muss.

Stellt die genannte existierende Implementierung allerdings balancierte Suchbäume zur Verfügung, fällt ein Großteil dieser Nachteile weg.

Ähnlich wie [[Bubblesort]] wird Binary Tree Sort kaum bei realen Problemen eingesetzt.

== Implementierung ==

Eine Beispielimplementierung in der Programmiersprache [[Perl (Programmiersprache)|Perl]]:

<syntaxhighlight lang="Perl">
use Tree::Binary::Search;
use Tree::Binary::Visitor::InOrderTraversal;

# Legt die zu sortierenden Elemente fest
my @zuSortierendeElemente = ( 'Birne', 'Apfel', 'Kirsche', 'Banane', 'Erdbeere', 'Zwiebel', 'Orange' );

# Hier wird ein binärer Suchbaum erzeugt
my $tree = Tree::Binary::Search->new;
$tree->useStringComparison();

# In der Schleife werden alle Elemente eingefügt
for $element (@zuSortierendeElemente) {
$tree->insert($element, $element);
}

# Der Baum wird schließlich in-order durchlaufen, und die Knoten werden in dieser Reihenfolge ausgegeben
my $visitor = Tree::Binary::Visitor::InOrderTraversal->new;
$tree->accept($visitor);
print join(", ", $visitor->getResults()) . "\n";
</syntaxhighlight>

== Treesort ==

Der Binary-Tree-Sort-Algorithmus ist nicht mit dem [[Treesort]]-Algorithmus von [[Robert Floyd|Floyd]]<ref>{{Literatur |Autor=[[Robert Floyd|Robert W. Floyd]] |Titel=Algorithm 113: Treesort |Sammelwerk=Communications of the ACM |Band=5 |Nummer=8 |Datum=1962-08 |Seiten=434}}</ref> oder ähnlichen Tree-Selection-Sortieralgorithmen<ref>{{BibISBN|0201896850|Seite=141–145}}</ref><ref>[https://xlinux.nist.gov/dads/HTML/treesort2.html nist.gov]</ref> zu verwechseln. Diese Algorithmen bauen nicht elementweise einen binären Baum auf, sondern interpretieren die zu sortierende Eingabe als vollständigen Binärbaum und haben eine asymptotisch optimale Laufzeit von <math>\mathcal{O}(n\log n)</math>. Der Treesort-Algorithmus ist ein Vorgänger von dem [[Heapsort]]-Algorithmus, wobei Heapsort eine bessere Laufzeit hat und weniger zusätzlichen Speicher benötigt.

== Einzelnachweise ==
<references />

[[Kategorie:Sortieralgorithmus]]

Binary Tree Sort - Versionsgeschichte

imported>Crazy1880: Vorlagen-fix (Datum)