Vorlesung Informatik 2 - Teil B: Theorie
4.7 Balancierte Bäume
Die Höhe eines Baums ist die maximale Tiefe seiner Knoten. Ein Knoten ohne Kinder hat also die Höhe 1 (manche Lehrbücher definieren die Höhe eines Baumes ohne Kinder auch als 0).
Rekursiv kann man die Höhe als 1 plus die maximale Höhe seiner Teilbäume definieren.
Ein Balancierter Baum mit n Knoten garantiert eine maximale Höhe von k log(n) wobei k eine von n unabhängige Konstante ist.
Die maximale Pfadlänge in einem balancierten Baum hat also die Komplexität O(logN).
Für jeden Knoten in einem balancierten Baum unterscheidet sich die Höhe seiner Teilbäume nur um eine bestimmte Differenz, auch Balance-Faktor oder Balance genannt.
Beispiel: Wir schreiben im der Suchbaum aus den Buchstaben des Wortes INDIANER an jeden Knoten K seine Höhe h und seine Balance b als bKh, die Balance ist dabei die Differenz der Höhe von rechtem und linkem Teilbaum.
0I3
/ \
0D2 1N2
/ \ \
0A1 0E1 0R1
Dieser Baum ist optimal balanciert, denn der höchste Balance-Faktor ist 1 am Knoten N.
Hier ein Beispiel für einen weniger balancierten Baum:
-2F4
/ \
-2D3 0K1
/
1A2
\
0B1 Der höchste Balance-Faktor ist hier -2 an den Knoten F und D. Berechnen Sie selbst die Balance-Faktoren und die Höhe für verschiedene Knoten.
Wenn es also gelingt, einen Suchbaum zu balancieren, hätten wir eine assoziative Datenstruktur (Map), die sowohl beim Einfügen als auch beim Suchen die Komplexität O(N) garantiert. Voraussetzung ist natürlich, dass das Balancieren keine höhere Komplexität hat.
Solche Bäume gibt es, die einfachsten sind die AVL Bäume des nächsten Kapitels. Davon abgeleitet sind weitere balancierte Suchbäume: 2-3-4- Bäume, Rot-Schwarz Bäume und B-Bäume.
Diese Datenstrukturen bilden heute das Rückgrat jeder Datenbank oder Suchmaschine und sind in Anwendungen wie dem Internet, Data-Mining und vielen anderen Techniken unverzichtbar.