Komplexität balancierter Bäume

Balancierte Suchbäume halten die Höhe klein genug, dass Suche, Einfügen und Löschen im Worst Case logarithmisch bleiben. Unbalancierte BSTs können zu linearen Ketten entarten.

Schwerpunkt: Invariante nennen, eine Rotation skizzieren, Komplexität begründen.

SLA-Argument: Suche und Update bleiben logarithmisch statt in schiefen Bäumen linear auszuufern. Relevant für Latenz-Percentile, nicht nur für Mittelwerte.

Vertiefung

In einem balancierten Suchbaum bleibt die Höhe proportional zum Logarithmus der Knotenzahl. Suche, Einfügepfad und Löschpfad folgen höchstens einem Wurzel-Blatt-Pfad und erben daher diese Schranke.

Rotationen oder Umfärbungen fügen nur begrenzte lokale Arbeit pro besuchter Ebene hinzu. Die Balancepflege ändert somit die Grössenordnung der Pfadoperationen nicht, verhindert aber den linearen Entartungsfall.

Ein vollständiger Durchlauf bleibt linear, weil jedes Element ausgegeben werden muss. Balance beschleunigt also nicht jede Operation, sondern vor allem solche, die Teilbäume über Ordnungsinformation ausschliessen.

Schwierigkeitsstufen

1. Pfadlänge aus einer Balancegarantie ableiten.
2. Sucharbeit und lokale Reparaturarbeit zusammensetzen.
3. Operationen erkennen, die trotz Balance linear bleiben.

Fallstricke

Die Garantie gilt nur, wenn die Balanceinvariante nach jeder Änderung erhalten wird. Ein sortierter Eingabestrom ist für einen unbalancierten Suchbaum weiterhin problematisch.