( B` ) 1

 Datenstruktur

 74 views
of 19
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Gewichtsbalancierte Suchbäume ã Gewichtsbalancierte oder BB-Bäume (bounded balance): Zulässige Abweichung der Struktur vom ausgeglichenen Binärbaum wird…
Share
Transcript
Gewichtsbalancierte Suchbäume • Gewichtsbalancierte oder BB-Bäume (bounded balance): Zulässige Abweichung der Struktur vom ausgeglichenen Binärbaum wird als Differenz zwischen der Anzahl der Knoten im rechten und linken Unterbaum festgelegt. Definition: Sei B ein binärer Suchbaum mit linkem Unterbaum Bl und l die Anzahl der Blätter in Bl (n sei entsprechend die gesamte Anzahl der Blätter in B) (1)  ( B ) = l / n heißt die Wurzelbalance von B. (2) Ein Baum B heißt gewichtsbalanciert (BB ( )) oder von beschränkter Balance , wenn für jeden Unterbaum B‘ von B gilt:    ( B‘ )  1 -  G.Heyer 1 Algorithmen und Datenstrukturen Parameter  als Freiheitsgrad im Baum •  = 1/2 : Balancierungskriterium akzeptiert nur vollständige Binärbäume •  < 1/2 : Strukturbeschränkung wird zunehmend gelockert ==> Welche Auswirkungen hat die Lockerung des Balancierungskriteriums auf die Kosten? Rebalancierung _ • wird gewährleistet durch die Wahl von   1 - V2 / 2 • Einsatz derselben Rotationstypen wie beim AVL - Baum Kosten für Suche und Aktualisierung: O ( log 2 n ) G.Heyer 2 Algorithmen und Datenstrukturen 11. Kapitel: Mehrwegbäume Definition: Ein m-Wege-Suchbaum oder ein m-ärer Suchbaum B ist ein Baum, in dem alle Knoten einen Grad  m besitzen. Entweder ist B leer oder er hat folgende Eingenschaften: 1) Jeder Knoten des Baums hat folgende Struktur: b * K1 D1 * K2 D2 * ... Kb Db * P0 P1 P2 Pb Die Pi , 0  i  b , sind Zeiger auf die Unterbäume des Knotens und die Ki und Di , 1  i  b sind Schlüsselwerte und Daten G.Heyer 3 Algorithmen und Datenstrukturen 2) Die Schlüsselwerte im Knoten sind aufsteigend geordnet: Ki  Ki+1 , 1  i < b . 3) Alle Schlüsselwerte im Unterbaum von Pi sind kleiner als der Schlüsselwert Ki+1, 0  i < b . 4) Alle Schlüsselwerte im Unterbaum von Pb sind größer als der Schlüsselwert Kb. 5) Die Unterbäume von Pi, 0  i  b sind auch m-Wege-Suchbäume. Die Di können Daten oder Zeiger auf die Daten repräsentieren. Zur Vereinfachung werden die Di weggelassen. G.Heyer 4 Algorithmen und Datenstrukturen Wichtige Eigenschaften für alle Mehrwegbäume: S( Pi ) sei die Seite, auf die Pi zeigt, und K(Pi) die Menge aller Schlüssel, die im Unterbaum mit Wurzel S(Pi) gespeichert werden können. Dann gelten folgende Ungleichungen: 1) x  K( P0 ) : x < K1 2) x  K( Pi ) : Ki < x < Ki +1 für i = 1, 2, ... , b-1 3) x  K( Pb ) : Kb< x G.Heyer 5 Algorithmen und Datenstrukturen Kostenanalyse: • Die Anzahl der Knoten N in einem vollständigen Baum der Höhe h , h  1, ist h N=  mi i=0 • Im ungünstigsten Fall ist der Baum völlig entartet: N=h • Schranken für die Höhe eines m-Wege Suchbaums: logm (N +1 )  h  N G.Heyer 6 Algorithmen und Datenstrukturen m-Wege-Suchbäume Definition des Knotenformats #define Emax M-1 /* maximale Anzahl von Einträgen */ typedef int Index ; /* 0 ... Emax -1*/ typedef struct { Schluesseltyp Key; Infotype Info; Sptr Ptr; } Eintrag ; typedef struct { Index b; /* Aktuelle Anzahl von Einträgen */ Sptr P0 ; Eintrag Evektor [Emax]; } Seite ; typedef Seite *Sptr; G.Heyer 7 Algorithmen und Datenstrukturen Rekursive Prozedur zum Aufsuchen eines Schlüssels void Msuche (Schluesseltyp X, Sptr P, Eintrag Element) { Index i; if ( P == NULL ) printf („Schluessel X ist nicht im Baum ! \n“); else { if ( X < P --> Evektor[ 0 ].Key) /* X < K1 */ Msuche ( X, P --> P0, Element); else { i = 0 ; while ( ( i < P --> b-1 ) && ( X > P --> Evektor[ i ].Key) ) i++; } if ( P --> Evektor[ i ].Key == X) /* Ki =X, 0  i  b-1 */ Element = P --> Evektor [i]; /* Ki < X < K i+1, 0  i  b-1 oder X > Kb */ else Msuche( X , P --> Evektor[ i ].Ptr, Element ); } return ; } G.Heyer 8 Algorithmen und Datenstrukturen Durchlauf eines m-Wege-Suchbaums in symmetrischer Ordnung void Sym_ord( Sptr P) { Index i ; if ( P != NULL) { Sym_ord (P --> P0) ; for ( i = 0 ; i = P --> b -1 ; i++ ) { printf ( „ Schluessel: %s \n“, P --> Evektor[ i ].Key); Sym_ord ( P --> Evektor [ i ].Ptr ); } } return; } G.Heyer 9 Algorithmen und Datenstrukturen Ziel: Aufbau sehr breiter Bäume von geringer Höhe • in Bezug auf Knotenstruktur vollständig ausgeglichen • effiziente Durchführung der Grundoperationen • Zugriffsverhalten weitgehend unabhängig von Anzahl der Sätze Weiterentwicklung der Mehrwegbäume: B- und B*-Baum B-Baum: 1970 von R. Bayer und E. McCreight entwickelt. Idee: dynamische Reorganisation eines Mehrwegbaumes durch Splitten und Mischen von Seiten. Grundoperationen: • Einfügen eines Satzes • Löschen eines Satzes • direkter Schlüsselzugriff auf einen Satz • sortiert, sequentieller Zugriff auf alle Sätze G.Heyer 10 Algorithmen und Datenstrukturen B - Bäume Definition: Seien k, h ganze Zahlen, h  0 , k > 0. Ein B -Baum B der Klasse  ( k, h ) ist entweder ein leerer Baum oder ein geordneter Baum mit folgenden Eigenschaften: 1) Jeder Pfad von der Wurzel zu einem Blatt hat die gleiche Länge h. 2) Jeder Knoten außer der Wurzel und den Blättern hat mindestens k + 1 Söhne. Die Wurzel ist ein Blatt oder hat mindestens 2 Söhne. 3) Jeder Knoten hat höchstens 2k+1 Söhne. 4) Jedes Blatt mit der Ausnahme der Wurzel als Blatt hat mindestens k und höchstens 2k Einträge. G.Heyer 11 Algorithmen und Datenstrukturen Für einen B - Baum ergibt sich folgendes Knotenformat: L b * K1 D1 * K2 D2 * ... Kb Db * freier Platz P0 P1 P2 Pb Einträge: • Die Einträge für Schlüssel, Daten und Zeiger haben die festen Längen lb, lK, lD und lp. • Die Knoten- oder Seitengröße sei L. • Maximale Anzahl von Einträgen pro Knoten: L - lb - lp bmax = ------------ = 2k l K + lD + l p G.Heyer 12 Algorithmen und Datenstrukturen Reformulierung der Definition: 4) und 3): Eine Seite darf höchstens voll sein. 4) und 2): Jede Seite (außer der Wurzel) muss mindestens halb voll sein. Die Wurzel enthält mindestens einen Schlüssel. 1): Der Baum ist, was die Knotenstruktur angeht, vollständig ausgeglichen. Höhe h: Bei einem Baum der Klasse  ( k , h ) mit n Schlüsseln gilt für seine Höhe: log2k+1 ( n + 1)  h  logk+1 ((n + 1) / 2 ) + 1 für n  1 und h = 0 für n = 0 G.Heyer 13 Algorithmen und Datenstrukturen Balancierte Struktur: • unabhängig von der Schlüsselmenge • unabhängig von ihrer Einfüge-Reihenfolge ==> Wie wird das erreicht ? Einfügen in B-Bäumen Was passiert, wenn die Wurzel überläuft ? * K1 * K2 * . . . * K 2k * K2k+1 G.Heyer 14 Algorithmen und Datenstrukturen Fundamentale Operation: Split-Vorgang ==> Aufteilung der Schlüsselmenge nach folgendem Prinzip: K1 K2 . . . K k Kk + 1 Kk + 2 . . . K2k + 1 • mittlere Schlüssel (Median) wird zum Vaterknoten gereicht • Ggf. muss Vaterknoten angelegt werden (Anforderung einer neuen Seite) Hier wird eine neue Wurzel angelegt: * Kk + 1 * * K1 * K2 * . . . * K k * * Kk + 2 * . . . * K2k + 1 * G.Heyer 15 Algorithmen und Datenstrukturen • Blattüberlauf erzwingt Split-Vorgang, was Einfügung in den Vaterknoten (ggf: Wurzel ) impliziert. • Wenn dieser überläuft, folgt erneuter Split-Vorgang • Split-Vorgang der Wurzel führt zu neuer Wurzel; Höhe des Baumes erhöht sich um 1. Bei B-Bäumen ist das Wachstum von den Blättern zur Wurzel hin gerichtet. Einfügealgorithmus (ggf. rekursiv ) • Suche Einfüge-Position • Wenn Platz vorhanden ist, speichere Element, sonst schaffe Platz durch Split-Vorgang und füge ein. G.Heyer 16 Algorithmen und Datenstrukturen Split-Vorgang als allgemeines Wartungsprinzip . . . * Kn * Kn+1 * . . . Pn Pn + 1 * K1 * . . . * Kk * Kk+1 * . . . * K2 k * K2 k +1 * P0 P1 Pk-1 Pk Pk + 1 P2 k P2 k + 1 . . . * Kn * Kk + 1 * Kn +1 * . . . Pn + 1 Pn P‘ * K1 * . . . * K k * * Kk +2 * . . . * K2 k+1 * P0 P1 Pk Pk + 1 Pk + 2 P2 k + 1 G.Heyer 17 Algorithmen und Datenstrukturen Kostenmaße • Anzahl der zu holenden Seiten: f (fetch) • Anzahl der zu schreibenden Seiten : w ( write) Direkte Suche • f min = 1 : der Schlüssel befindet sich in der Wurzel • f max = h : der Schlüssel ist in einem Blatt • mittlere Zugriffskosten h - 1  f avg  h - 1 ( für h > 1 ) k 2k Beim B -Baum sind die maximalen Zugriffskosten h eine gute Abschätzung der mittleren Zugriffskosten. ==> Bei h = 3 und einem k = 100 ergibt sich 2.99  f avg  2.995 G.Heyer 18 Algorithmen und Datenstrukturen Sequentielle Suche • Durchlauf in symmetrischer Ordnung : f seq = N • Pufferung der Zwischenknoten im HSP wichtig ! Einfügen • Günstigster Fall - kein Split-Vorgang: fmin = h ; wmin = 1 • Durchschnittlicher Fall : favg = h ; wavg < 1 + 2 k G.Heyer 19 Algorithmen und Datenstrukturen
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks