a b Baum Der ist eine Datenstruktur in der Informatik und Spezialfall eines Baumes speziell eines Out Trees Abbildung 1

(a, b)-Baum

Der (a, b)-Baum ist eine Datenstruktur in der Informatik und Spezialfall eines Baumes speziell eines Out-Trees.

Abbildung 1: (2, 4)-Baum

Bei einem -Baum haben alle Teilbäume die gleiche Tiefe, und alle inneren Knoten – außer der Wurzel – haben zwischen und Kinder, wobei und natürliche Zahlen sind, die die Eigenschaft erfüllen müssen. Die Wurzel hat, falls sie kein Blatt ist, zwischen 2 und Kinder.

Die Schlüssel und Datenelemente werden nur in den Blättern gespeichert.

Definition Bearbeiten

Seien natürliche Zahlen mit . Dann ist der Out-Tree ein -Baum, falls gilt:

Für innere Knoten außer der Wurzel ist Ausgangsgrad .
Die Wurzel hat höchstens Kinder.
Alle Pfade von der Wurzel zu einem Blatt haben gleiche Tiefe

Kennzeichnung der inneren Knoten Bearbeiten

Jeder innere Knoten besteht aus folgenden Bezeichnern:

Sei die Anzahl der Kinder von .
Seien die Kanten zu den Kindern.
Sei eine sortierte Liste von Schlüsseln, wobei gleich dem größten Schlüssel im Teilbaum mit Wurzel ist.

Siehe auch Bearbeiten

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

Paul E. Black: (Memento vom 13. Oktober 2018 im Internet Archive) In: Vreda Pieterse, Paul E. Black (Hrsg.): Dictionary of Algorithms and Data Structures. 6. Oktober 2004, abgerufen am 20. Juni 2015.

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: Februar 16, 2024, 01:03 am

Der a b Baum ist eine Datenstruktur in der Informatik und Spezialfall eines Baumes speziell eines Out Trees Abbildung 1 2 4 BaumBei einem a b displaystyle a b Baum haben alle Teilbaume die gleiche Tiefe und alle inneren Knoten ausser der Wurzel haben zwischen a displaystyle a und b displaystyle b Kinder wobei a displaystyle a und b displaystyle b naturliche Zahlen sind die die Eigenschaft 2 a b 1 2 displaystyle 2 leq a leq b 1 2 erfullen mussen Die Wurzel hat falls sie kein Blatt ist zwischen 2 und b displaystyle b Kinder 1 Die Schlussel und Datenelemente werden nur in den Blattern gespeichert Inhaltsverzeichnis 1 Definition 2 Kennzeichnung der inneren Knoten 3 Siehe auch 4 Weblinks 5 EinzelnachweiseDefinition BearbeitenSeien a b N displaystyle a b in mathbb N nbsp naturliche Zahlen mit 2 a b 1 2 displaystyle 2 leq a leq b 1 2 nbsp Dann ist der Out Tree T displaystyle T nbsp ein a b displaystyle a b nbsp Baum falls gilt Fur innere Knoten ausser der Wurzel ist a displaystyle a leq nbsp Ausgangsgrad b displaystyle leq b nbsp Die Wurzel hat hochstens b displaystyle b nbsp Kinder Alle Pfade von der Wurzel zu einem Blatt haben gleiche TiefeKennzeichnung der inneren Knoten BearbeitenJeder innere Knoten v displaystyle v nbsp besteht aus folgenden Bezeichnern Sei r v displaystyle rho v nbsp die Anzahl der Kinder von v displaystyle v nbsp Seien S v 1 r v displaystyle S v 1 dots rho v nbsp die Kanten zu den Kindern Sei H v 1 r v 1 displaystyle H v 1 dots rho v 1 nbsp eine sortierte Liste von Schlusseln wobei H v i displaystyle H v i nbsp gleich dem grossten Schlussel im Teilbaum mit Wurzel S v i displaystyle S v i nbsp ist Siehe auch BearbeitenB Baum SuchbaumWeblinks Bearbeitenhttps tcs rwth aachen de lehre DA SS2011 handout 2011 05 03 pdf https daphne informatik uni freiburg de svn public AlgoDatSS2015 public folien vorlesung 08b pdfEinzelnachweise Bearbeiten Paul E Black a b tree Memento vom 13 Oktober 2018 im Internet Archive In Vreda Pieterse Paul E Black Hrsg Dictionary of Algorithms and Data Structures 6 Oktober 2004 abgerufen am 20 Juni 2015 Abgerufen von https de wikipedia org w index php title a b Baum amp oldid 229069790