Binary Tree Sort

Binary Tree Sort (im Deutschen auch Binarytreesort) ist ein einfacher, 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.

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) . Zudem wird für den aufzubauenden Suchbaum 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.

Ä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

Liste von Algorithmen


Wikimedia Foundation.

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

  • Tree sort — A tree sort is a sort algorithm that builds a binary search tree from the keys to be sorted, and then traverses the tree so that the keys come out in sorted order. Adding items to a binary search tree is an O(log(n)) process, so, therefore,… …   Wikipedia

  • Binary search tree — In computer science, a binary search tree (BST) is a binary tree data structurewhich has the following properties: *each node (item in the tree) has a value; *a total order (linear order) is defined on these values; *the left subtree of a node… …   Wikipedia

  • Binary space partitioning — (BSP) is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of the scene by means of a tree data structure known as a BSP tree.In simpler words, it is a method of breaking …   Wikipedia

  • Binary logarithm — NOTOC In mathematics, the binary logarithm (log2 n ) is the logarithm for base 2. It is the inverse function of n mapsto 2^n. The binary logarithm is often used in computer science and information theory (where it is frequently written lg n , or… …   Wikipedia

  • Insertion sort — Infobox Algorithm class=Sorting algorithm data=Array time= О(n²) space= О(n) total, O(1) auxiliary optimal=Not usuallyInsertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time …   Wikipedia

  • Self-balancing binary search tree — In computer science, a self balancing binary search tree or height balanced binary search tree is a binary search tree that attempts to keep its height , or the number of levels of nodes beneath the root, as small as possible at all times,… …   Wikipedia

  • Radix sort — In computer science, radix sort is a sorting algorithm that sorts integers by processing individual digits. Because integers can represent strings of characters (e.g., names or dates) and specially formatted floating point numbers, radix sort is… …   Wikipedia

  • Merge sort — Example of merge sort sorting a list of random dots. Class Sorting algorithm Data structure Array Worst case performance O(n log n) …   Wikipedia

  • B-tree — In computer science, a B tree is a tree data structure that keeps data sorted and allows searches, insertions, and deletions in logarithmic amortized time. It is most commonly used in databases and filesystems. In B trees, internal (non leaf)… …   Wikipedia

  • Kd-tree — In computer science, a k d tree (short for k dimensional tree ) is a space partitioning data structure for organizing points in a k dimensional space. k d trees are a useful data structure for several applications, such as searches involving a… …   Wikipedia

Share the article and excerpts

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