Wozu braucht man Binary Trees genau und wie funktionieren sie grob?
2 Antworten
Hallo,
Binärbäume habe ich vor vielen Jahren zum Sortieren von Daten verwendet.
Modell: Der erste Wert wird in der Wurzel abgelegt, der zweite Wert links davon, wenn er größer ist, und rechts davon wenn er kleiner ist.
Die Position im Binärbaum wird durch Verweise auf die Vorgängerposition und die beiden Nachfolgen (links und rechts) beschreiben.
Tatsächlich schreibt man die Daten physikalisch mit ihren Verweisen in eine sequentielle Datei. Beim Sortieren werden als keine Daten umpositioniert, sondern nur die Verweise ausgelesen. So kann die Reihenfolge der Daten sehr schnell gefunden werden.
Um die Effizienz zu steigern, habe ich zeitweise über Nacht den Baum ausgelesen und in einen idealen Baum, d.h. jedes Element hat genau zwei Nachfolger, umgewandelt.
LG Culles
Wie schon gesagt, zum Sortieren von Daten. Ich kann ja in einem Datenbestand nur etwas wiederfinden, wenn ich weiß, wo ich etwas abgelegt habe. Es gibt natürlich noch andere Sortiermethoden (Bubblesort, Quicksort, Mergesort ...), welche Algorithmen man heute im Allgemeinen verwendet, weiß ich leider nicht.
Binärbäume sind nur eine Ausprängung von Bäumen, der Name sagt es, sie haben (bis zu) 2 Kinder.
Der Codebaum eines Huffmancodes ist z.B: ein Binärbaum. Binäre Suchbäume können zum Suchen verwendet werden (die vermutlich häufigste Nutzung).
Danke erstmal… aber wo wird das Binärbaum-Prinzip wirklich angewendet, wo in real life?