Binarytreesort

Binary Tree Sort (im Deutschen auch Binarytreesort) ist ein einfacher, in seiner primitivsten Form nicht stabiler Sortieralgorithmus.

Inhaltsverzeichnis

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 bis zu den Blättern hinab sucht, z. B. FindDupGE, wird der Sortieralgorithmus stabil.

Komplexität

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

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

Vor- und Nachteile

Der Algorithmus wird üblicherweise anhand einer existierenden Implementation 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 und der große Aufwand für die einzelnen Operationen, der zusätzliche Speicherbedarf sowie die in Verhältnis zu seiner Effizienz aufwendige Implementierung, falls diese von Grund auf neu erfolgen muss.

Stellt die genannte existierende Implementation 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.

Implementierungen

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 in dieser Reihenfolge ausgegeben
 my $visitor = Tree::Binary::Visitor::InOrderTraversal->new;
 $tree->accept($visitor);
 print join(", ", $visitor->getResults()) . "\n";

Siehe auch


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Binary Tree Sort — (im Deutschen auch Binarytreesort) ist ein einfacher, nicht stabiler Sortieralgorithmus. Inhaltsverzeichnis 1 Prinzip 2 Komplexität 3 Vor und Nachteile 4 Implementierungen …   Deutsch Wikipedia

  • Binärer Suchbaum — der Höhe 5 mit 13 Knoten: Wurzel J und Blättern C, G, N, Q, U und X In der Informatik ist ein binärer Suchbaum eine spezielle Implementierung der abstrakten Datenstruktur Suchbaum. Ein binärer Suchbaum, häufig abgekürzt als BST (von englisch …   Deutsch Wikipedia

  • Liste von Algorithmen — Dies ist eine Liste von Artikeln zu Algorithmen in der deutschsprachigen Wikipedia. Siehe auch unter Datenstruktur für eine Liste von Datenstrukturen. Inhaltsverzeichnis 1 Klassen von Algorithmen nach Komplexität 2 Klassen von Algorithmen nach… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”