Balancierter Baum

Ein Balancierter Baum ist in der Informatik ein Spezialfall der Datenstruktur Baum, der eine maximale Höhe von c\cdot\log(n) garantiert, wobei n die Anzahl der Elemente im Baum angibt und c eine von n unabhängige Konstante ist. Manche Autoren rechnen auch Datenstrukturen dazu, die Vorkehrungen enthalten, dass die Höhe im Mittel logarithmisch bleibt.

Inhaltsverzeichnis

Problem: Entartung

Die wichtigste Anwendung von Bäumen in der Informatik ist die als Suchbaum. Die Laufzeit der wichtigsten Operationen in einem Suchbaum (Suchen, Einfügen oder Löschen eines Wertes) hängt im schlechtesten Fall linear von der Höhe des Baumes ab (die Operationen haben eine Komplexität von O(h); h Höhe des Baumes).

Jeder

Beispiel für nicht balancierten Baum

Fügt man jedoch zum Beispiel einem Suchbaum eine große Menge bereits sortierter Daten ein, wächst dieser ungleichmäßig und hat im Extremfall eine Höhe von n mit der unerwünschten Folge, dass auch jede folgende Einfüge-, Such- und Löschoperation der Komplexität O(n) ist.

Ein zu einer Liste entarteter Suchbaum

Siehe auch: O-Notation, Komplexität, Erwartungswert

Gegenstrategie: Balance halten

Balancierte Bäume wurden entwickelt, um die Entartung zu verhindern und eine Höhe von c\cdot\log(n) zu garantieren.

Dazu verfolgt man unterschiedliche Konzepte. Allen gemeinsam ist: Man fordert spezielle Eigenschaften des Baumes,

  • aus denen folgt, dass die Höhe des Baumes in jedem Fall c\cdot\log(n) ist.
  • sodass es geeignete Such-, Einfüge- und Löschoperationen (sinnvollerweise der Komplexität O(h)) gibt, die die speziellen Eigenschaften wahren.

Man erhält eine solche Operation, indem man die Operation der allgemeinen Suchbäume verwendet und nach jeder Ausführung an der Stelle der Änderung die Balance überprüft, adjustiert und ggf. neu balanciert. Es kann vorkommen, dass sich diese Anpassungs- und Reparatur-Welle bis zur Wurzel hinauf fortsetzt.

Höhenbalance

Nach der Höhe balancierte Bäume stellen für jeden Knoten sicher, dass die Höhe des linken Unterbaumes und die Höhe des rechten Unterbaumes nur um ein bestimmtes Verhältnis oder eine bestimmte Differenz voneinander abweichen.

Beim Rot-Schwarz-Baum wird jedem Knoten eine Farbe (rot oder schwarz) zugeordnet; der Baum ist bezüglich der schwarzen Knoten optimal höhenbalanciert und der Anteil der roten Knoten ist begrenzt. Diese Bäume stellen eine binäre Realisierung der 2-3-4-Bäume dar, einer speziellen Variante der B-Bäume.

Im AVL-Baum gilt für jeden Knoten: Die Höhe seines linken Kindes weicht von der seines rechten Kindes um höchstens ±1 ab.

Gewichtsbalance

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.
Allerdings kann bei einer extremen Verteilung der Zugriffswahrscheinlichkeiten auch beim optimalen gewichteten binären Suchbaum eine lineare (nicht mehr logarithmische) Abhängigkeit der Höhe von der Anzahl herauskommen.

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.

Dies und noch mehr leisten die Splay-Bäume.

Mehlhorn führt gewichtsbalancierte BB[α]-Bäume ein. Hier gilt für jeden Knoten: Die Anzahl der Knoten (das Gewicht) links unter ihm steht in einem gewissen Verhältnis zu der Gesamtanzahl der Knoten unter ihm (und damit auch in einem gewissen Verhältnis zu der Anzahl der Knoten rechts unter ihm).

Siehe auch

Literatur

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

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Balancierter Suchbaum — Ein Balancierter Baum ist in der Informatik ein Spezialfall der Datenstruktur Baum, der eine maximale Höhe von garantiert, wobei n die Anzahl der Elemente im Baum angibt und c eine von n unabhängige Konstante ist. Inhaltsverzeichnis 1 Problem:… …   Deutsch Wikipedia

  • Baum (Datenstruktur) — Ein Baum ist in der Graphentheorie ein spezieller Graph, mit dem sich eine Monohierarchie modellieren lässt. Je nachdem, ob die Kanten des Baums eine ausgezeichnete Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in… …   Deutsch Wikipedia

  • Baum (Informatik) — Ein Baum ist in der Graphentheorie ein spezieller Graph, mit dem sich eine Monohierarchie modellieren lässt. Je nachdem, ob die Kanten des Baums eine ausgezeichnete Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in… …   Deutsch Wikipedia

  • Binärer Baum — Ein voller, aber nicht vollständiger Binärbaum Als Binärbaum bezeichnet man in der Graphentheorie eine spezielle Form eines Graphen. Genauer gesagt handelt es sich um einen gewurzelten Baum, bei dem jeder Knoten höchstens zwei Kindknoten besitzt …   Deutsch Wikipedia

  • Bayer-Baum — Ein B Baum ist in der Informatik eine Daten oder Indexstruktur, die häufig in Datenbanken und Dateisystemen eingesetzt wird. Ein B Baum ist ein immer vollständig balancierter Baum, der Daten sortiert nach Schlüsseln speichert. Das Einfügen,… …   Deutsch Wikipedia

  • B-Baum — Ein B Baum (englisch B tree) ist in der Informatik eine Daten oder Indexstruktur, die häufig in Datenbanken und Dateisystemen eingesetzt wird. Ein B Baum ist ein immer vollständig balancierter Baum, der Daten sortiert nach Schlüsseln… …   Deutsch Wikipedia

  • Schwarz-Rot-Baum — Ein Rot Schwarz Baum ist in der Informatik eine vom binären Suchbaum abgeleitete Datenstruktur, die sehr schnellen Zugriff auf die in ihr gespeicherten Werte garantiert. Rot Schwarz Bäume wurden zuerst 1972 von Rudolf Bayer beschrieben[1],… …   Deutsch Wikipedia

  • K-d-Baum — Ein k dimensionaler Baum oder k d Baum ist ein balancierter Suchbaum zur Speicherung von Punkten aus dem . Er bietet ähnlich dem Bereichsbaum die Möglichkeit, orthogonale Bereichsanfragen durchzuführen. Die Anfragekomplexität ist zwar höher,… …   Deutsch Wikipedia

  • Kd-Baum — Ein k dimensionaler Baum oder k d Baum ist ein balancierter Suchbaum zur Speicherung von Punkten aus dem . Er bietet ähnlich dem Bereichsbaum die Möglichkeit, orthogonale Bereichsanfragen durchzuführen. Die Anfragekomplexität ist zwar höher,… …   Deutsch Wikipedia

  • 2-4-Baum — 2 3 4 Baum Ein 2 3 4 Baum ist in der Informatik eine Datenstruktur, genauer ein B Baum der Ordnung 4, das heißt, er ist ein Baum, in dem jeder Knoten zwei, drei oder maximal vier Kinder besitzt und entsprechend ein, zwei oder maximal drei… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”