imported>DixMartin: +Link Gewicht

2020-02-22T09:25:26Z

+Link Gewicht

Neue Seite

[[File:binary_search_tree_with_weights.svg|thumb|220px|Ein binärer Suchbaum mit 2 Knoten und Gewichtsangaben (rot)]]

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

Zu optimieren ist die [[Gewichteter binärer Suchbaum#Zugriffsverteilung und gewichtete Pfadlänge|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 [[Balancierter Baum|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 <math>p_i = (1-q) q^i</math> für <math>i = 0,1,...</math> mit <math>0 < q < 1</math> gilt <math>\textstyle\sum_{i \geqq 0}p_i = 1</math>. 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 <math>\textstyle \sum_{i \geqq 0}(i+1)p_i = 1/(1-q)</math>, obwohl er einer linearen Liste entspricht.
Passt nun die Anordnung der Schlüssel genau zu diesem Binärbaum (so dass er ein binärer ''Such''baum ist), so ist er bei <math>q>\tfrac12</math> 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 <math>i</math>-t häufigsten Wortes ungefähr
:<math>\alpha_i \approx i^{-1{,}12} / \sum_{i \geqq 1}i^{-1{,}12}</math>.
Die gewichtete Pfadlänge eines optimalen binären Suchbaums für ''alle'' englischen Wörter ergibt sich zu ungefähr <math>10{,}2</math>.

=== 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.

[[Kurt Mehlhorn|Mehlhorn]] beschreibt „Nahezu optimale binäre Suchbäume“.

Bei den [[Splay-Baum|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 ==
[[File:Binary search tree with weights +.svg|thumb|306px|Abb. 4: (Optimaler) binärer Suchbaum mit Gewichten (rot).]]
Sei <math> X := \left\{ x_1 < x_2 < ... < x_n \right\}</math> eine Schlüsselmenge aus einem [[Totale Quasiordnung|total (quasi)geordneten]] Reservoir <math>R</math> von Schlüsseln, seien ferner <math>p_i</math> bzw. <math>q_j</math> Häufigkeiten, mit denen auf das Element <math>x \in R</math> (oder Äquivalenzklasse resp. Intervall) zugegriffen wird, wobei <math>x \in \overline{x_i}</math> für <math>1 \leqq i \leqq n</math> resp. <math>x_j < x < x_{j+1}</math> für <math>0 \leqq j \leqq n</math>. (Dabei seien <math>x_0 := -\infty</math> und <math>x_{n+1} := +\infty</math> zusätzliche nicht zu <math>R</math> gehörende Elemente mit der üblichen Bedeutung.) Das <math> (2n+1)</math>-[[Tupel]]
:<math>\mathfrak{z} := \left(\begin{smallmatrix}
& p_1 && p_2 && \cdots && p_n & \\
q_0 && q_1 && q_2 && \cdots && q_n
\end{smallmatrix}\right)</math>
heißt '''Zugriffsverteilung'''<ref>nach [[#Mehlhorn]] a. a. O. S. 147</ref> für die Menge <math>X</math>, wenn alle <math>p_i, q_j \geqq 0</math> sind. <math>\mathfrak{z}</math> wird zur '''Zugriffswahrscheinlichkeitsverteilung''', wenn <math>\textstyle \sum p_i + \sum q_j = 1</math> ist.

Sei nun <math> T</math> ein Suchbaum für die Menge <math>X</math> mit einer Zugriffsverteilung <math>\mathfrak{z}</math>, ferner sei <math>a_i^T</math> die [[Gewurzelter Baum#Weitere Begriffe|Tiefe]] des (inneren) Knotens <math> x_i</math> und <math>b_j^T</math> die Tiefe des Blattes <math>(x_j, x_{j+1})</math> (s. Abb. 4; jeweils [[Binärer Suchbaum#Terminologie]] der Abb. 1B). Wir betrachten die Suche nach einem Element <math>x \in R</math>. Wenn <math>x = x_i</math>, dann vergleichen wir <math>x</math> mit <math>a_i^T+1</math> Elementen im Baum. Wenn <math>x_j < x < x_{j+1}</math>, dann vergleichen wir <math>x</math> mit <math>b_j^T</math>Elementen im Baum. Also ist
:<math>S^T_{\mathfrak{z}} := \sum_{i=1}^n p_i (a_i^T+1) + \sum_{j=0}^n q_j b_j^T</math>
die (mit der Zugriffsverteilung <math>\mathfrak{z}</math>) '''gewichtete Pfadlängensumme''' des Baumes <math>T</math>; ist <math>\mathfrak{z}</math> eine Wahrscheinlichkeitsverteilung, dann ist <math>S^T_{\mathfrak{z}}</math> die '''gewichtete Pfadlänge''', die '''gewichtete Suchtiefe''' oder die mittlere Anzahl der benötigten Vergleiche. Die Abb. 4 zeigt einen Suchbaum <math>T</math>, der mit einem Wert von <math>S^T_{\mathfrak{z}}=2</math> optimal für die Zugriffsverteilung <math>\mathfrak{z} := \tfrac1{24} \left(\begin{smallmatrix}
& 1 && 3 && 3 && 0 & \\
4 && 0 && 0 && 3 && 10
\end{smallmatrix}\right)</math> ist.

== Literatur ==
* {{Anker|Mehlhorn}}Kurt Mehlhorn: ''Datenstrukturen und effiziente Algorithmen.'' Teubner, Stuttgart 1988, ISBN 3-519-12255-3.

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4157275-0|REMARK=Ansetzungsform GND: „Gewichteter Binärbaum“.}}

{{DEFAULTSORT:Gewichteter Binarer Suchbaum}}
[[Kategorie:Suchbaum]]

[[en:Binary search tree#Optimal binary search trees]]

Gewichteter binärer Suchbaum - Versionsgeschichte

imported>DixMartin: +Link Gewicht