Binary Tree Sort

Binary Tree Sort ist ein einfacher, in seiner primitivsten Form nicht stabiler Sortieralgorithmus.

Prinzip

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

In seiner ganz elementaren Form ist der Algorithmus nicht stabil. Wird jedoch statt der üblichsten Suchfunktion 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 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. FindDupGE.

Komplexität

Die durchschnittliche Komplexität beträgt ${\displaystyle {\mathcal {O}}(n\log n)}$, im Worst Case einer bereits sortierten Liste ist sie jedoch ${\displaystyle \Theta (n^{2})}$. Wird statt des unbalancierten ein balancierter binärer Suchbaum genommen, ist die Komplexität auch im Worst Case ${\displaystyle {\mathcal {O}}(n\log n)}$.

Für den aufzubauenden Suchbaum wird ${\displaystyle {\mathcal {O}}(n)}$ zusätzlicher Speicher benötigt.

Vor- und Nachteile

Der Algorithmus wird üblicherweise anhand einer existierenden Implementierung zur Verwaltung und Manipulation von 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 Operationen, der zusätzliche Speicherbedarf sowie die im Verhältnis zu seiner 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:

 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";

Treesort

Der Binary-Tree-Sort-Algorithmus ist nicht mit dem Treesort-Algorithmus von Floyd^[1] oder ähnlichen Tree-Selection-Sortieralgorithmen^[2][3] 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 ${\displaystyle {\mathcal {O}}(n\log n)}$. 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

1. Robert W. Floyd: Algorithm 113: Treesort. In: Communications of the ACM. Band 5, Nr. 8, August 1962, S. 434.
2. Donald E. Knuth: The Art of Computer Programming. 2. Auflage. Volume 3: Sorting and Searching. Addison-Wesley, Reading MA 1997, ISBN 0-201-89685-0, S. 141–145 (englisch).
3. nist.gov