Gewichteter binärer Suchbaum

Grundidee gewichteter Suchbäume

Ein gewichteter binärer Suchbaum ist ein binärer Suchbaum, bei dem jeder Knoten zusätzlich zu Schlüssel und Daten ein Gewicht besitzt. Dieses Gewicht beschreibt die Zugriffswahrscheinlichkeit des Schlüssels; auch den Nachbarintervallen zwischen den Schlüsseln kommt ein Gewicht zu.

Ziel ist es, die gewichtete Pfadlänge zu minimieren. Häufig abgefragte Schlüssel sollen deshalb möglichst nahe an der Wurzel liegen, damit im Durchschnitt wenige Vergleiche nötig sind. Das Gewicht ist an den Schlüssel gebunden; mehrere Objekte mit demselben Schlüssel („Duplikate“) sind daher nicht sinnvoll.

Sind keine Gewichte bekannt oder nahezu alle gleich, eignen sich höhenbalancierte Bäume. Der AVL-Baum kann dabei als für Einheitsgewichte auf die gewichtete Pfadlänge optimiert angesehen werden.

Zugriffsverteilung und mittlere Vergleichszahl

Für die geordneten Schlüssel X := {x₁ < x₂ < ... < xₙ} werden pᵢ als Zugriffshäufigkeiten auf Schlüssel beziehungsweise deren Äquivalenzklassen verwendet. Die qⱼ beschreiben Zugriffe auf die Zwischenintervalle xⱼ < x < xⱼ₊₁, wobei x₀ := −∞ und xₙ₊₁ := +∞ sind.

Das (2n+1)-Tupel aus allen pᵢ und qⱼ heißt Zugriffsverteilung, wenn alle pᵢ, qⱼ ≥ 0 gelten. Es ist eine Zugriffswahrscheinlichkeitsverteilung, wenn ∑pᵢ + ∑qⱼ = 1 ist.

Hat der innere Knoten xᵢ im Baum T die Tiefe aᵢᵀ und das Blatt für das Intervall (xⱼ,xⱼ₊₁) die Tiefe bⱼᵀ, dann lautet die gewichtete Pfadlängensumme:

S_z^T := ∑ᵢ₌₁ⁿ pᵢ(aᵢᵀ+1) + ∑ⱼ₌₀ⁿ qⱼbⱼᵀ.

Bei einer Wahrscheinlichkeitsverteilung ist S_z^T die gewichtete Pfadlänge, gewichtete Suchtiefe oder mittlere Anzahl benötigter Vergleiche. Im dargestellten Beispiel ist ein Baum mit S_z^T = 2 optimal für z := 1/24 · ((1,3,3,0); (4,0,0,3,10)).

Statische und dynamische Gewichte

Bei einem statischen Baum, bei dem Einfüge- und Entfernoperationen keine Rolle spielen, kann der Bellman-Algorithmus einen optimalen gewichteten binären Suchbaum konstruieren. Er ist auch effizient, wenn die Gewichte nur ungefähr bekannt sind.

Wenn Einfüge- oder Entfernoperationen wichtig sind, müssen grundsätzlich auch die Gewichte gepflegt werden. Im Grenzfall geschieht dies bereits beim Aufsuchen eines Elements, weil sich dabei die Zugriffsstatistik verändert. Mehlhorn beschreibt hierfür „Nahezu optimale binäre Suchbäume“. Splay-Bäume verfolgen ein anderes Verfahren, bringen aber ebenfalls besonders häufig angesprochene Knoten in die Nähe der Wurzel.

Beispiele für ungleiche Zugriffshäufigkeiten

Bei der geometrischen Gewichtsverteilung pᵢ = (1−q)qᶦ für i = 0,1,... und 0 < q < 1 gilt ∑ᵢ≥0 pᵢ = 1. Wird rekursiv jeweils der Schlüssel mit dem größten verbleibenden Gewicht zu einem Sohn und zur Wurzel des nächsten Teilbaums gemacht, bleibt der andere Sohn leer. Der Baum entspricht damit einer linearen Liste, hat aber die konstante gewichtete Pfadlänge ∑ᵢ≥0(i+1)pᵢ = 1/(1−q).

Passt die Schlüsselreihenfolge zu diesem Baum, sodass er ein binärer Suchbaum ist, dann ist er für q > 1/2 optimal: Das Herabstufen einer Teilbaumwurzel verschlechtert den Mittelwert. Sehr seltene Suchanfragen können also selbst im optimalen gewichteten Baum lineare Zeit benötigen.

Für englische Wörter wird die Wahrscheinlichkeit des i-t-häufigsten Wortes näherungsweise durch αᵢ ≈ i^−1,12 / ∑ᵢ≥1 i^−1,12 beschrieben. Die gewichtete Pfadlänge eines optimalen binären Suchbaums für alle englischen Wörter beträgt ungefähr 10,2.