Balancierte Bäume

Effizienz der Wörterbuchoperationen auf Bäumen hängt direkt von der Baumhöhe ab.

Baum mit n Knoten:

Mindesthöhe: |_log2 n_|, maximale Höhe: n-1

Zugriff im Mittel O(log2 n), aber worst case linear.

Ziel:

schneller direkter Zugriff mit z max ? O ( log2 n),

Einfüge- und Löschoperationen mit logarithmischen Aufwand

Heuristik:

für jeden Knoten im Baum soll die Anzahl der Knoten in jedem seiner beiden Unterbäume möglichst gleich gehalten werden