Balancierte Bäume
← Traversierung des Gesamtbaums | ● | Baumrotation →
Entspricht ein Baum von der Topologie her einer Liste, so nennt man einen solchen Baum degeneriert.
Dann ist der Suchaufwand nicht besser als bei einer Liste.
Einen degenerierten Baum erhält man zum Beispiel, wenn bereits sortierte Elemente eingefügt werden.
Die einfachste Gegenstrategie zur Verhinderung der Degeneration ist das Einfügen der Elemente in einer zufälligen Reihenfolge.
Ist andererseits eine bestimmte Reihenfolge vorgegeben, so wendet man die Gegenstrategie der Balancierung an:
Dies bedeutet, dass zusätzliche Eigenschaften des binären Baums gefordert werden, welche die Degeneration verhindern. Falls nach dem Einfügen eines Elements diese Eigenschaften verletzt wurden, so wird der entstandene Baum topologisch umstrukturiert, so dass die geforderten Eigenschaften wieder erfüllt sind.
Balancierungsmethoden:
| Methode | geforderte Eigenschaft | maximale Baumtiefe |
|---|---|---|
| AVL Bäume | die Tiefe des linken und rechten Teilbaums differiert nicht mehr als 1 | $1.44log_2n$ |
| Red/Black Trees | Abwechselnd Rot und Schwarz gefärbte Knoten | $2log_2n$ |
| Random BS Trees | Element mit Wahrscheinlichkeit $p=\frac1{k+1}$ zur Wurzel machen | $\approx 4 log_2n$ |
Weiterführende Literatur:
Weitere von Bäumen abgeleitete oder verwandte Datenstrukturen:
Sonstige Datenstrukturen:
- Assoziatives Array
- Hashing
usw.