Gewichteter binärer Suchbaum

Ein binärer Suchbaum mit 2 Knoten und Gewichtsangaben (rot)

In der Informatik ist ein gewichteter binärer Suchbaum eine Ausprägung der abstrakten Datenstruktur binärer Suchbaum, bei der jedem Knoten neben Schlüssel und anderen Daten ein Gewicht (Zugriffswahrscheinlichkeit) zukommt. (Der Vollständigkeit halber kommt ein solches auch seinen Nachbarintervallen zu.)

Zu optimieren ist die gewichtete Pfadlänge des Baums.

Das Gewicht ist an den Schlüssel gebunden, somit ergibt das Zulassen von mehreren Objekten („Duplikaten“) mit gleichem Schlüssel keinen Sinn.

Sind Gewichte überhaupt nicht bekannt oder sind sie untereinander praktisch gleich, dann sind höhen-balancierte Bäume eine gute Wahl. Ein Beispiel ist der AVL-Baum, der als optimiert auf die gewichtete Pfadlänge bei Einheitsgewichten angesehen werden kann.

Beispiele

Ist der Baum statisch, spielen also Einfüge- oder Entfernoperationen keine Rolle, so bietet sich der Bellman-Algorithmus an, der einen optimalen gewichteten binären Suchbaum konstruiert. Seine Effizienz ist auch dann gegeben, wenn die Gewichte nur ungefähr bekannt sind.

Geometrische Verteilung

Bei der geometrischen Gewichtsverteilung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_i = (1-q) q^i} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i = 0,1,...} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0 < q < 1} gilt $\textstyle \sum _{i\geqq 0}p_{i}=1$. Ein Binärbaum sei wie folgt rekursiv aufgebaut: Derjenige Schlüssel wird zu einem der beiden Söhne und zur Wurzel des nächsten Teilbaums gemacht, der das größte verbleibende Gewicht hat. Da es danach keinen Schlüssel auf seiner Seite mehr gibt, bleibt der andere Sohn leer. Ein solcher Binärbaum hat die konstante gewichtete Pfadlänge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textstyle \sum_{i \geqq 0}(i+1)p_i = 1/(1-q)} , obwohl er einer linearen Liste entspricht. Passt nun die Anordnung der Schlüssel genau zu diesem Binärbaum (so dass er ein binärer Suchbaum ist), so ist er bei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q>\tfrac12} optimal, denn ein Herabstufen der Wurzel eines Teilbaums verschlechtert den Mittelwert. Es gibt dann also sehr seltene Suchanfragen, die beim optimalen gewichteten binären Suchbaum in nur linearer Zeit beantwortet werden.

Natürliche Vokabulare

Im Englischen ist die Wahrscheinlichkeit für das Vorkommen des $i$-t häufigsten Wortes ungefähr

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \alpha_i \approx i^{-1{,}12} / \sum_{i \geqq 1}i^{-1{,}12}} .

Die gewichtete Pfadlänge eines optimalen binären Suchbaums für alle englischen Wörter ergibt sich zu ungefähr Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 10{,}2} .

Dynamische Gewichte

Sind Einfüge- oder Entfernoperationen wichtig, so sind im Prinzip auch die Gewichte zu pflegen. Im Grenzfall sogar beim Aufsuchen, da sich hierbei zumindest die Zugriffsstatistik ändert.

Mehlhorn beschreibt „Nahezu optimale binäre Suchbäume“.

Bei den Splay-Bäumen werden trotz völlig anderer Vorgehensweise ebenfalls die am häufigsten angesprochenen Knoten in die Nähe der Wurzel gespült.

Zugriffsverteilung und gewichtete Pfadlänge

Abb. 4: (Optimaler) binärer Suchbaum mit Gewichten (rot).

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X := \left\{ x_1 < x_2 < ... < x_n \right\}} eine Schlüsselmenge aus einem total (quasi)geordneten Reservoir Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} von Schlüsseln, seien ferner Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_i} bzw. $q_{j}$ Häufigkeiten, mit denen auf das Element Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \in R} (oder Äquivalenzklasse resp. Intervall) zugegriffen wird, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \in \overline{x_i}} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \leqq i \leqq n} resp. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_j < x < x_{j+1}} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0 \leqq j \leqq n} . (Dabei seien $x_{0}:=-\infty$ und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{n+1} := +\infty} zusätzliche nicht zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} gehörende Elemente mit der üblichen Bedeutung.) Das Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (2n+1)} -Tupel

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{z} := \left(\begin{smallmatrix} & p_1 && p_2 && \cdots && p_n & \\ q_0 && q_1 && q_2 && \cdots && q_n \end{smallmatrix}\right)}

heißt Zugriffsverteilung für die Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} , wenn alle Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle p_{i},q_{j}\geqq 0} sind. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{z}} wird zur Zugriffswahrscheinlichkeitsverteilung, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textstyle \sum p_i + \sum q_j = 1} ist.

Sei nun $T$ ein Suchbaum für die Menge $X$ mit einer Zugriffsverteilung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{z}} , ferner sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_i^T} die Tiefe des (inneren) Knotens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_j^T} die Tiefe des Blattes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x_j, x_{j+1})} (s. Abb. 4; jeweils Binärer Suchbaum#Terminologie der Abb. 1B). Wir betrachten die Suche nach einem Element $x\in R$. Wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x = x_i} , dann vergleichen wir $x$ mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_i^T+1} Elementen im Baum. Wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_j < x < x_{j+1}} , dann vergleichen wir Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_j^T} Elementen im Baum. Also ist

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S^T_{\mathfrak{z}} := \sum_{i=1}^n p_i (a_i^T+1) + \sum_{j=0}^n q_j b_j^T}

die (mit der Zugriffsverteilung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{z}} ) gewichtete Pfadlängensumme des Baumes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T} ; ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{z}} eine Wahrscheinlichkeitsverteilung, dann ist $S_{\mathfrak {z}}^{T}$ die gewichtete Pfadlänge, die gewichtete Suchtiefe oder die mittlere Anzahl der benötigten Vergleiche. Die Abb. 4 zeigt einen Suchbaum Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T} , der mit einem Wert von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S^T_{\mathfrak{z}}=2} optimal für die Zugriffsverteilung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{z} := \tfrac1{24} \left(\begin{smallmatrix} & 1 && 3 && 3 && 0 & \\ 4 && 0 && 0 && 3 && 10 \end{smallmatrix}\right)} ist.

Literatur

• Kurt Mehlhorn: Datenstrukturen und effiziente Algorithmen. Teubner, Stuttgart 1988, ISBN 3-519-12255-3.