Gewichteter binärer Suchbaum

Begriff der Informatik

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

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

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

Bearbeiten

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

Bearbeiten

Bei der geometrischen Gewichtsverteilung   für   mit   gilt  . 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  , 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   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

Bearbeiten

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

 .

Die gewichtete Pfadlänge eines optimalen binären Suchbaums für alle englischen Wörter ergibt sich zu ungefähr  .

Dynamische Gewichte

Bearbeiten

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

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

Sei   eine Schlüsselmenge aus einem total (quasi)geordneten Reservoir   von Schlüsseln, seien ferner   bzw.   Häufigkeiten, mit denen auf das Element   (oder Äquivalenzklasse resp. Intervall) zugegriffen wird, wobei   für   resp.   für  . (Dabei seien   und   zusätzliche nicht zu   gehörende Elemente mit der üblichen Bedeutung.) Das  -Tupel

 

heißt Zugriffsverteilung[1] für die Menge  , wenn alle   sind.   wird zur Zugriffswahrscheinlichkeitsverteilung, wenn   ist.

Sei nun   ein Suchbaum für die Menge   mit einer Zugriffsverteilung  , ferner sei   die Tiefe des (inneren) Knotens   und   die Tiefe des Blattes   (s. Abb. 4; jeweils Binärer Suchbaum#Terminologie der Abb. 1B). Wir betrachten die Suche nach einem Element  . Wenn  , dann vergleichen wir   mit   Elementen im Baum. Wenn  , dann vergleichen wir   mit  Elementen im Baum. Also ist

 

die (mit der Zugriffsverteilung  ) gewichtete Pfadlängensumme des Baumes  ; ist   eine Wahrscheinlichkeitsverteilung, dann ist   die gewichtete Pfadlänge, die gewichtete Suchtiefe oder die mittlere Anzahl der benötigten Vergleiche. Die Abb. 4 zeigt einen Suchbaum  , der mit einem Wert von   optimal für die Zugriffsverteilung   ist.

Literatur

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

Einzelnachweise

Bearbeiten
  1. nach #Mehlhorn a. a. O. S. 147