miaowang.de - Binary Tree Sort

Binary Tree Sort

Binary Tree Sort ist die Bezeichnung eine Menge an Daten mit Hilfe des binären Suchbaums zu sortieren.

gute Komplexität

stabil möglich (die Reihenfolge von schon sortierten Elementen ändert sich nach Sortierung nicht)

in-place (bzw. in-situ, d.h. es wird kein zusätzlicher Speicher benötigt)

online (kann Folge sortieren, während es sie erhält)

Idee

Die zu sortierende Elemente werden einfach in einem binären Suchbaum gespeichert. Um die Elemente in einer sortierten Reihenfolge zu erhalten, muss der Baum nur inorder traversiert werden. Da ein einfacher binärer Suchbaum in eine lineare Datenstruktur entarten kann, ist es vorteilhafter eine balancierte Version eines binären Suchbaums zu nutzen (AVL-Baum, Rot-Schwarz-Baum)

Applet

Das Applet (benötigt Java) visualisiert einen BinaryTreeSort auf maximal 16 Elemente und einer maximalen Baumhöhe von 4. Mit Insert lassen sich Werte zur Folge/Baum hinzufügen und mit Clear löscht man die aktuelle Folge/Baum. Mit Show as ... kann man zwischen Baum- und Listenansicht hin- und herschalten.

Varianten

HeapSort benutzt ebenfalss eine Baumstruktur, jedoch eine Heap-Datenstruktur anstatt eines binären Suchbaums.

Analysé

Das Einfügen eines Elements in einen binären Suchbaum benötigt O(log n) Zeit. Für n Elemente wären das insgesamt O(n log n) Zeit. Die Inorder-Traversierung benötigt nur O(n).

Weiterführende Links und Literatur

Last Update: 05.04.2011 02:46:53