1. Definition - Was sind Bayer-Bäume?

• entwickelt 1970 von R. Bayer und E.McCreight
• baumartige Struktur
• mindestens 50% Speicherauslastung
• hoher Verwaltungsaufwand
• schneller Zugriff auf Daten
• besonders geeignet für große Datenmengen
• immer ausgeglichen
  
  unausgeglichener Binärer-Baum, kann nie auftreten

1. Die Ordnung eines Baumes wird als n bezeichnet.
2. Jeder Knoten enthält eine Anzahl von m Elementen, wobei n <= m <= 2n.
3. Die Wurzel eines Baumes darf weniger als n Elemente enthalten.
4. Jeder Knoten, der kein Blatt ist, hat m+1 Nachfolger (Unterbäume).
5. Alle Blätter liegen auf der selben Ebene.
6. Die Anzahl der Ebenen eines Baumes wird als h bezeichnet.
7. Jedes Element hat einen Schlüssel über das es eindeutig idendifiziert werden und in den Baum an die korrekte Stelle eingefügt werden kann

• Ordnung n = 2
• Höhe des Baumes h = 3

• einem Zeiger auf den Unterbaum, rechts vom Element
• der Schlüssel des Elementes
• die eigentlichen Daten des Elementes (Info-Komponente)

TElement = Record
  	   { der Schlüssel des Elementes }
	   Key: KeyTyp;
	   { die eigentlichen Daten des Elementes }
	   Info: InfoTyp;
	   { der Unterbaum des Elementes,
  	     der sich rechts vom Element befindet }
	   Link: LinkTyp;
           End;

• einem Feld mit den Elementen des Knotens
• die Anzahl der Elemente in dem Knoten

PKnoten = ^TKnoten;
TKnoten = Record
	  { Elemente des Knotens }
          Elemente: Array [0..2*n] of TElement;
          { Anzahl der Elemente im Knoten }
          Anzahl: Integer;
          End;