Balancierte Binärbäume
2 unterschiedliche Vorgehensweisen:
(1) die zulässige Höhendifferenz der beiden Unterbäume ist beschränkt
==> höhenbalancierte Bäume
(2) das Verhältnis der Knotengewichte der beiden Unterbäume erfüllt gewisse Bedingungen.
==> gewichtsbalancierte Bäume
Zu (1) Definition: Seien Bl(x) und Br(x) die linken und rechten Unterbäume eines Knotens x. Weiterhin sei h (B) die Höhe eines Baumes B. Ein k-balancierter Binärbaum ist entweder leer oder es ist ein Baum, bei dem für jeden Knoten x gilt:
| h (B l ( x ) - h (B r ( x )) | ? k
k läßt sich als Maß für die zulässige Entartung im Vergleich zur ausgeglichenen Baumstruktur auffassen.