www.wikidata.de-de.nina.az

Balancierter Baum Ein balancierter Baum englisch oft self balancing tree ist in der Informatik ein Spezialfall der Daten

Balancierter Baum

Ein balancierter Baum (englisch oft self-balancing tree) ist in der Informatik ein Spezialfall der Datenstruktur Baum, der eine maximale Höhe von garantiert, wobei die Anzahl der Elemente im Baum angibt und eine von unabhängige Konstante ist. Manche Autoren rechnen auch Datenstrukturen dazu, die Vorkehrungen enthalten, dass die mittlere Höhe oder Pfadlänge bei jedem Baum logarithmisch bleibt.

Problem: Entartung Bearbeiten

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

Jeder k-näre Baum mit Knoten hat eine Höhe von ; und im Durchschnitt immer noch für ein gewisses konstantes . So sind auch die Operationen auf einem Baum mindestens der Komplexität .

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 mit der unerwünschten Folge, dass auch jede folgende Einfüge-, Such- und Löschoperation der Komplexität ist.

Ein zu einer Liste entarteter Suchbaum

Das Ergebnis dieses einseitigen Einfügens wäre somit eine einfach verkettete Liste; die Vorteile eines Baums wären somit zunichtegemacht

Gegenstrategie: Balance halten Bearbeiten

Balancierte Bäume wurden entwickelt, um die Entartung zu verhindern und eine Höhe von 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 ist.
  • sodass es geeignete Such-, Einfüge- und Löschoperationen (sinnvollerweise der Komplexität ) 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 Bearbeiten

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.

Balance der Knotenzahl Bearbeiten

Sei ein Binärbaum mit linkem Unterbaum und rechtem Unterbaum . Dann heißt

die Wurzelbalance von . Dabei bedeutet die Anzahl der (externen) Blätter von .

Ein Binärbaum wird von beschränkter Balance α genannt, wenn für jeden Unterbaum von gilt:

Diese Art Binärbäume wurden 1972 von Reingold und Nievergelt eingeführt. In der englischen Literatur heißen sie auch „weight-balanced trees“ (WBTs).

Mehlhorn versammelt alle Binärbäume mit beschränkter Balance α in der Menge BB(α) und beweist auf S. 181:
Sei und T ein BB(α)-Baum. Dann haben die Operationen Suche(a,T), Einfüge(a,T), Lösche(a,T) jeweils die Zeitkomplexität .

Gewichtsbalance Bearbeiten

Unter dem Gewicht eines Knotens sei hier die Wahrscheinlichkeit des Zugriffs auf ihn verstanden.

Ist der Baum statisch, spielen also Einfüge- oder Löschoperationen 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 im worst case 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.

Siehe auch Bearbeiten

Einzelnachweise Bearbeiten

  1. Nievergelt, J. & Reingold, E. M. (1972) Binary search trees of bounded balance. In Proceedings of the Fourth Annual Acm Symposium on Theory of Computing. ACM, pp. 137–142.
  2. Y. Hirai, K. Yamamoto: Balancing weight-balanced trees. In: J. Functional Programming. 21. Jahrgang, Nr. 3, 2011, S. 287, doi:10.1017/S0956796811000104 (yoichihirai.com [PDF]).

Literatur Bearbeiten

  • Kurt Mehlhorn Datenstrukturen und effiziente Algorithmen Teubner Stuttgart 1988, ISBN 3-519-12255-3.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Ein balancierter Baum englisch oft self balancing tree ist in der Informatik ein Spezialfall der Datenstruktur Baum der eine maximale Hohe von c log n displaystyle c cdot log n garantiert wobei n displaystyle n die Anzahl der Elemente im Baum angibt und c displaystyle c eine von n displaystyle n unabhangige Konstante ist Manche Autoren rechnen auch Datenstrukturen dazu die Vorkehrungen enthalten dass die mittlere Hohe oder Pfadlange bei jedem Baum logarithmisch bleibt Inhaltsverzeichnis 1 Problem Entartung 2 Gegenstrategie Balance halten 2 1 Hohenbalance 2 2 Balance der Knotenzahl 2 3 Gewichtsbalance 3 Siehe auch 4 Einzelnachweise 5 LiteraturProblem Entartung BearbeitenEine wichtige Anwendung von Baumen in der Informatik ist deren Nutzung als Suchbaum Die Laufzeit der wichtigsten Operationen in einem Suchbaum Suchen Einfugen und Loschen eines Wertes hangt im schlechtesten Fall linear von der Hohe des Baumes ab die Operationen haben eine Komplexitat von O h displaystyle mathcal O h nbsp h displaystyle h nbsp Hohe des Baumes Jeder k nare Baum mit n displaystyle n nbsp Knoten hat eine Hohe von h log k n 1 displaystyle h geq log k n 1 nbsp und im Durchschnitt immer noch c log k n displaystyle c cdot log k n nbsp fur ein gewisses konstantes c displaystyle c nbsp So sind auch die Operationen auf einem Baum mindestens der Komplexitat O log k n O log n displaystyle mathcal O log k n mathcal O log n nbsp nbsp Beispiel fur nicht balancierten BaumFugt man jedoch zum Beispiel einem Suchbaum eine grosse Menge bereits sortierter Daten ein wachst dieser ungleichmassig und hat im Extremfall eine Hohe von n displaystyle n nbsp mit der unerwunschten Folge dass auch jede folgende Einfuge Such und Loschoperation der Komplexitat O n displaystyle mathcal O n nbsp ist nbsp Ein zu einer Liste entarteter SuchbaumDas Ergebnis dieses einseitigen Einfugens ware somit eine einfach verkettete Liste die Vorteile eines Baums waren somit zunichtegemacht Siehe auch O Notation Komplexitat und ErwartungswertGegenstrategie Balance halten BearbeitenBalancierte Baume wurden entwickelt um die Entartung zu verhindern und eine Hohe von c log n displaystyle c cdot log n nbsp zu garantieren Dazu verfolgt man unterschiedliche Konzepte Allen gemeinsam ist Man fordert spezielle Eigenschaften des Baumes aus denen folgt dass die Hohe des Baumes in jedem Fall c log n displaystyle c cdot log n nbsp ist sodass es geeignete Such Einfuge und Loschoperationen sinnvollerweise der Komplexitat O h displaystyle mathcal O h nbsp gibt die die speziellen Eigenschaften wahren Man erhalt eine solche Operation indem man die Operation der allgemeinen Suchbaume verwendet und nach jeder Ausfuhrung an der Stelle der Anderung die Balance uberpruft adjustiert und ggf neu balanciert Es kann vorkommen dass sich diese Anpassungs und Reparatur Welle bis zur Wurzel hinauf fortsetzt Hohenbalance Bearbeiten Nach der Hohe balancierte Baume stellen fur jeden Knoten sicher dass die Hohe des linken Unterbaumes und die Hohe des rechten Unterbaumes nur um ein bestimmtes Verhaltnis oder eine bestimmte Differenz voneinander abweichen Beim Rot Schwarz Baum wird jedem Knoten eine Farbe Rot oder Schwarz zugeordnet der Baum ist bezuglich der schwarzen Knoten optimal hohenbalanciert und der Anteil der roten Knoten ist begrenzt Diese Baume stellen eine binare Realisierung der 2 3 4 Baume dar einer speziellen Variante der B Baume Im AVL Baum gilt fur jeden Knoten Die Hohe seines linken Kindes weicht von der seines rechten Kindes um hochstens 1 ab Balance der Knotenzahl Bearbeiten Sei T displaystyle T nbsp ein Binarbaum mit linkem Unterbaum T l displaystyle T l nbsp und rechtem Unterbaum T r displaystyle T r nbsp Dann heisst r T T l T 1 T r T displaystyle rho T tfrac T l T 1 tfrac T r T nbsp die Wurzelbalance von T displaystyle T nbsp Dabei bedeutet T displaystyle T nbsp die Anzahl der externen Blatter von T displaystyle T nbsp Ein Binarbaum wird von beschrankter Balance a genannt wenn fur jeden Unterbaum T displaystyle T nbsp von T displaystyle T nbsp gilt a r T 1 a displaystyle alpha leq rho T leq 1 alpha nbsp Diese Art Binarbaume wurden 1972 von Reingold und Nievergelt 1 eingefuhrt In der englischen Literatur heissen sie auch weight balanced trees WBTs 2 Mehlhorn versammelt alle Binarbaume mit beschrankter Balance a in der Menge BB a und beweist auf S 181 Sei 1 4 lt a 1 2 2 displaystyle tfrac 1 4 lt alpha leq 1 tfrac sqrt 2 2 nbsp und T ein BB a Baum Dann haben die Operationen Suche a T Einfuge a T Losche a T jeweils die Zeitkomplexitat O log T displaystyle mathcal mathcal O log T nbsp Gewichtsbalance Bearbeiten Unter dem Gewicht eines Knotens sei hier die Wahrscheinlichkeit des Zugriffs auf ihn verstanden Ist der Baum statisch spielen also Einfuge oder Loschoperationen keine Rolle so bietet sich der Bellman Algorithmus an der einen optimalen gewichteten binaren Suchbaum konstruiert Seine Effizienz ist auch dann gegeben wenn die Gewichte nur ungefahr bekannt sind Allerdings kann bei einer extremen Verteilung der Zugriffswahrscheinlichkeiten auch beim optimalen gewichteten binaren Suchbaum im worst case eine lineare nicht mehr logarithmische Abhangigkeit der Hohe von der Anzahl herauskommen Sind Einfuge oder Entfernoperationen wichtig so sind im Prinzip auch die Gewichte zu pflegen Im Grenzfall sogar beim Aufsuchen da sich hierbei zumindest die Zugriffsstatistik andert Dies und noch mehr leisten die Splay Baume Siehe auch BearbeitenGewichteter binarer Suchbaum Bellman Algorithmus Konstruktion des optimalen gewichteten binaren Suchbaums Splay BaumEinzelnachweise Bearbeiten Nievergelt J amp Reingold E M 1972 Binary search trees of bounded balance In Proceedings of the Fourth Annual Acm Symposium on Theory of Computing ACM pp 137 142 Y Hirai K Yamamoto Balancing weight balanced trees In J Functional Programming 21 Jahrgang Nr 3 2011 S 287 doi 10 1017 S0956796811000104 yoichihirai com PDF Literatur BearbeitenKurt Mehlhorn Datenstrukturen und effiziente Algorithmen Teubner Stuttgart 1988 ISBN 3 519 12255 3 Abgerufen von https de wikipedia org w index php title Balancierter Baum amp oldid 231734132