Binärbäume haben genau zwei Nachfolgerzeiger. Damit verdoppelt sich die Anzahl der Knoten mit jeder Stufe des Baumes. Ein ausgeglichener Binärbaum der Höhe n umfasst 2n - 1 Knoten und Blätter.
Ausgeglichener Binäbaum
Solche Bäume werden häufig zum Sortieren von Daten verwendet. Dabei bezeichnet man z.B. die Zeiger mit pLinks und pRechts, entsprechend der graphischen Struktur des Baumes. Der Zeiger pLinks zeigt auf einen Teilbaum, dessen für die Sortierung relevanten Daten alle kleiner als der eigene Datenwert ist, der Zeiger pRechts auf einen Teilbaum mit nur größeren Daten.
Sortiert man in dem oben dargestellten Baum die Zahlen 1 bis 15, so ergibt sich folgender Baum:
Neue Daten werden dabei von der Wurzel aus so eingefügt, dass ein Datum jeweils dem Zeiger pLinks zugeordnet wird, wenn es kleiner ist als das Datum des Knoten, sonst dem Zeiger pRechts. Dies erfolgt solange, bis ein Zeiger den Wert nil enthält. Hier wird das Datum als neues Blatt eingefügt.
Hierbei entstehen oft Bäume, die sehr unterschiedlich lange Äste haben, also unausgeglichen sind. Zur optimalen Suche im Baum sollte dieser allerdings ausgeglichen sein. Hierfür gibt es Algorithmen, die diese Aufgabe erledigen.
Die Suche nach einem bestimmten Datum reduziert sich in einem ausgeglichenen Baum auf einen Aufwand von log2 n, wenn n die Anzahl der Daten ist. Man muss nämlich maximal die Tiefe des Baumes durchlaufen, um das gewünschte Datum zu erhalten. Vergleicht man das Ergebnis mit dem Suchen in einer Liste, wo man das gewünschte Datum vielleicht erst gegen Ende der Liste auffindet, so erkennt man den Gewinn insbesondere bei großer Datenzahl. Dort liegt ein Aufwand proportional zu n vor.
Bei 1000 Daten muss man im Schnitt etwa 500 Daten durchsuchen, bei einem sortierten ausgeglichenen Binärbaum maximal 10, da die Höhe des Baumes 10 beträgt, denn dieser enthält 210 - 1 = 1023 mögliche Daten. (log2 1000 ist ungefähr 10)
Autor: Jürgen Dehmer
Letzte Änderung: 17. Februar 2001