Listen und Bäume

 

Beim Programmieren muß man sich häufig Gedanken darüber machen, wie das selbstgeschriebene Programm mit größeren linearen Datenmengen umgehen soll. Ist die Anzahl der Datensätze mehr oder weniger fest, so ist dies kein Problem: Arrays z.B. können entsprechend dimensioniert werden.

Was aber, wenn sich die Größe eines Arrays während der Laufzeit fortwährend ändert? Insbesondere, wenn gar keine obere Grenze für die Datenmenge angegeben werden kann? Die Größe eines Arrays fortlaufend zu ändern, bzw. neue Arrays anzulegen und deren Elemente zu kopieren ist keine hilfreiche Lösung. Eine bessere Alternative sind Listen.

Bei Listen handelt es sich um Datenstrukturen, die neben den eigentlichen Nutzdaten noch einen Zeiger auf die jeweilige nächste Datenstruktur enthalten. Für die richtige Anordnung sorgt ein Merkmal der Daten, z.B. ein aufsteigender Index. Auf diese Art und Weise lassen sich Daten verketten; Lösch- und Einfügeoperationen für veraltete/neue Daten gestalten sich relativ einfach: man sucht die richtige Position aus (durch Vergleiche) und biegt den Zeiger auf das nächste bzw. einzufügende Element um.

Möchte man innerhalb dieser verketteten Liste nach ganz bestimmten Datenelementen suchen, so muß man mehr oder weniger die gesamte Liste durchstöbern, bis das gewünschte Element gefunden wird. Bei sehr großen Datenmengen kann dies sehr langwierig und unpraktikabel sein. Aber auch hierfür gibt es einen Ausweg: Binärbäume.

Bei den modernen Programmiersprachen wie z.B. Java und C# gibt es meist Sprachkonstrukte, die genau diese Listen bereits fertig implementiert haben.

Bei Binärbäumen (genaueres dazu hier) besitzt ein Datenelement nicht bloß einen Zeiger auf das nächste Datenelement, sondern zwei. Auch hier wird die richtige Einfügeoperation mittels Vergleiche ermittelt. Bei der Suche können auf diese Weise können auch größere Datenmengen sehr effizient traversiert werden: bei 1000 Datensätzen müssen im Schnitt nur etwa 10 Datensätze verglichen werden.

Es gibt aber auch Fälle, bei denen Binärbäume sehr inhomogen aufgebaut sind. Wenn z.B. durch ungünstige Anordnungen immer nur einer der beiden Zeiger auf einen Nachfolger verweist, entartet der Baum wieder zu einer linearen Kette – mit derselben nachteiligen Sucheigenschaft. Man kann also versuchen, Binärbäume durch geschicktes Umordnen auszubalancieren. Eines der gängigsten Verfahren hierzu ist der AVL-Baum.

Dateibäume finden auch in der Astronomie Verwendung. Die n-Körper-Rechnung z.B. ist mit steigender Zahl n sehr rechenintensiv. Über Baumstrukturen können Massen zu größeren Einheiten kombiniert werden, um weniger Körper rechnen zu müssen. Beim Treecode-Verfahren beispielsweise können die Positionen der Massen in einer dreidimensionalen Struktur abgelegt werden. Statt zweier Nachfolgeelemente hat jede Datenstruktur acht.

Quellen: Wikipedia (inkl. Grafiken)