Definition 1.1: Ein Graph G ist ein geordnetes Paar (V,E) aus einer Menge V von Knoten und einer Menge E von Kanten. Auf E ist eine Abbildung, die Inzidenzfunktion erklaert, die jedem Element von E eindeutig ein geordnetes oder ungeordnetes Paar von V zuordnet. [Bronstein]
Definition 1.2: Sind die Paare von Knoten eines Graphen ungeordnet, so heisst der Graph ungerichteter Graph. Sind die Paare von Knoten eines Graphen geordnet, so heisst der Graph gerichtet oder Digraph. [Bronstein]
Definiton 1.3: Sind zwei Knoten eines Graphen durch einen Bogen oder eine Kante miteinander verbunden, so heissen die Knoten adjazent. [Bronstein]
Definition 1.4.1: In gerichteten Graphen wird eine Folge
von Boegen Kette der Laenge s, wenn F keinen Bogen zweimal enthaelt
und fuer 
jeder Bogen e
einen seiner Endpunkte
mit dem Bogen e
und den anderen mit e
gemeinsam hat.
[Bronstein]
Definition 1.4.2: Eine geschlossene Kette wird Zyklus genannt. [Bronstein]
Definition 1.4.3: Eine Kette heisst Bahn, wenn fuer i=1,2,...,s-1 der
Zielpunkt des Bogens e mit dem Startpunkt des Bogens e
uebereinstimmt. [Bronstein]
Definition 1.4.4: Eine geschlossene Bahn, in der jeder Knoten Endpunkt genau zweier Boegen ist, heisst Kreis. [Bronstein]
Definition 1.4.5: Als Grad d
eines Knoten bezeichnet
man die Anzahl der mit v inzidierenden Kanten oder Boegen. Knoten vom Grad 0
heissen isolierte Knoten. [Bronstein]
Definiton 2.1: Ein ungerichteter zusammenhaengender Graph, in dem kein Kreis existiert, wird Baum genannt. Jeder Baum mit mindestens zwei Knoten enthaelt mindestens zwei Knoten vom Grad 1. Jeder Baum mit der Knotenzahl n hat genau n-1 Kanten. [Bronstein]
Definition 2.2: Ein Baum mit einem ausgezeichneten Knoten wird Wurzelbaum genannt, und der ausgezeichnete Knoten heisst Wurzel. Im Bild eines Wurzelbaumes wird die Wurzel in der Regel oben angeordnet, und die Wege werden von der Wurzel weggerichtet betrachtet. Wurzelbaeume dienen zur graphischen Darstellung hierarchischer Strukturen, wie z.B. Befehlsfluesse in Betrieben, Stammbaeume, grammatikalische Strukturen. [Bronstein]
Definition 2.3: Hat ein Wurzelbaum nur Knoten vom Grad 1, 2 oder 3, so heisst er Binaerbaum. [Bronstein]
Definition 2.4: Hat ein binaerer Baum genau einen Knoten vom Grad 2 und sonst
nur Knoten vom Grad 1 oder 3, dann wird er regulaerer binaerer Baum
oder voller Binaerbaum genannt. Die Knotenanzahl in regulaeren binaeren
Baeumen ist ungerade. Regulaere Baeume mit der Knotenzahl n haben 
Knoten vom Grad 1. [Bronstein]
Definition 2.5: Die Knoten vom Grad 1 heissen externe Knoten oder Blaetter des Binaerbaums. [Bronstein]
Definition 2.6: In einem regulaeren binaeren Baum heissen alle Knoten, die keine Blaetter sind, interne Knoten. [Booth] [Cormen]
Definition 2.7: Das Niveau eines Knoten ist sein Abstand von der Wurzel. [Bronstein]
Definition 2.8: Das maximal auftretende Niveau eines Baumes wird Hoehe des Baumes genannt. [Bronstein]
Ein Binaerbaum ist am besten rekursiv beschreibbar: Ein Binaerbaum T ist eine auf eine endliche, positive Anzahl von Knoten definierte Datenstruktur, die entweder
Definition 2.10: Ist der linke Unterbaum der Wurzel eines Binaerbaumes T nicht leer, so wird die Wurzel des linken Unterbaumes linkes Kind der Wurzel von T genannt. Ist der rechte Unterbaum der Wurzel von T nicht leer, so wird die Wurzel des rechten Unterbaumes rechtes Kind der Wurzel von T genannt. Die Wurzel von T heisst dann Elternknoten des linken und rechten Kindes. [Cormen]
Das Bild 2 zeigt einen indizierten Binaerbaum. In diesem wird jedem Knoten ein ,,Index'' zugeordnet. Diese Indizierung dient der Unterscheidung der einzelnen Knoten.
Baeume und Graphen besitzen in der Informatik ein grosses Anwendungsgebiet. Ein Anwendungsbeispiel fuer Binaerbaeume sind z.B. Woerterbuecher. Obwohl Binaerbaeume ohne besondere Spezifikationen fuer viele Anwendungen ausreichend sind, gibt es Gefahren bei der Benutzung von ``normalen'' Binaerbaeumen. Obwohl der Aufwand, der benoetigt wird, um ein Element zu suchen, zu loeschen, oder einzufuegen im Durchschnitt von der Groessenordnung O(log n) ist, sind die worst case Kosten dieser Operationen in einem Binaerbaum O(n). Um jedoch alle Operationen (Entnehmen, Loeschen, Einfuegen) in der Datenstruktur Baum so schnell wie moeglich zu halten, wurden mehrere Theorien und Algorithmen entwickelt, auf die wir im naechsten Kapitel eingehen werden.
