Definition:

Ein Baum besteht aus einer Wurzel, Knoten oder Blättern und Verweisen (Zeigern) auch Kanten genannt. Wenn ein Baum aus Datenobjekten besteht, die genau zwei Verweise (Zeiger) enthalten, die auf andere Knoten des Baumes gerichtet sind, spricht man von einem Binärbaum.

Vorteile: Kurze Zugriffszeiten, beim Suchen und Sortieren (O(log n)) gegenüber einfach verketteten Listen (O(n))

Begriffe:

Wurzel: Ist der Knoten, zu dem selbst kein anderes Element zeigt, d.h. der oberste Knoten.

Knoten: Von hier gehen Verzweigungen zu weiteren Elementen aus.

Endknoten: Ist ein Knoten, der auf kein weiteres Element zeigt. Die Zeiger des Endknotens sollten also “geerdet” sein. Endknoten werden auch Blatt genannt.

Teilbaum: Ein Teilbaum ist ein Baum, dessen Wurzel ein Knoten eines anderen Baumes ist.

Pfad: Der Weg von der Wurzel zu einem bestimmten Knoten oder Blatt.

Baumarten:

geordneter Baum: Ein Baum ist geordnet, wenn von jeder Knoten aus stets links kleinere und rechts größere Elemente stehen.

entarteter Baum: Ein Baum ist entartet, wenn von jedem Knoten nur jeweils eine Verzweigung ausgeht.

AVL-Bäume: AVL-Bäume sind ausgeglichene Bäume auch ausgewogen oder höhenbalanciert genannt. Ein Baum ist ausgeglichen, wenn sich für jeden Knoten die Höhe der von ihm ausgehenden Teilbäume um höchstens 1 unterscheidet. Die Höhendifferenz wird auch Balance genannt.

Suchbaum: Datenstruktur, in die man Objekte mit ihren Schlüsseln leicht und schnell einsortieren und wieder finden kann. Schlüssel sind Elemente oder Kombinationen von Elementen eines Datensatzes zur eindeutigen Identifizierung eines Datensatzes.

B-Baum: Datenstruktur zur Verwaltung umfangreicher, oft benutzter Datenmengen auf einem Massenspeicher. Dieser Baum ist ein ausgeglichener Baum, alle Blätter liegen auf einem Niveau.

Einfügen eines Knotens:

Fall 1: Überhang “außen” im linken Teilbaum. Sohnknoten: -1 Vaterknoten: -2 linkslastig

Fall 2: Überhang “außen” im rechten Teilbaum. Sohnknoten: +1 Vaterknoten: +2 rechtslastig

Fall 3: Überhang “innen” (Mitte) im linken Teilbaum. Sohnknoten: +1 Vaterknoten: -2 linkslastig

Fall 4: Überhang “innen” (Mitte) im rechten Teilbaum. Sohnknoten:-1 Vaterknoten: +2 rechtslastig Symmetrisch zu Fall 3. Erst Rotation nach rechts und dann nach links.

Löschen von Knoten:

Fall 1: Der zu löschende Knoten ist ein Blatt, hat also keine Nachfolger. Er kann also einfach aus dem Baum genommen werden.

Fall 2: Der zu löschende Knoten hat einen Sohn, auf der linken oder rechten Seite. Der Knoten wird gelöscht und sein Sohn wird der Sohn seines Vorgängers.

Fall 3: Der zu löschende Sohn hat zwei Söhne. Variante 1: der am weiten links stehende Knoten im Rechten Teilbaum kommt an die Stelle des zu löschenden Knoten Variante 2: der größte Knoten im linken Teilbaum ersetzt den zu entfernenden Knoten

Baumdurchlauf

Da bei Bäumen nur ein indirektrer Zugriff auf die Knoten möglich ist, benötigt man Algorithmen um jeden einzelnen Knoten besuchen zu können.

• Inorder-Durchlauf: links, anzeigen, rechts
• Preorder-Durchlauf: anzeigen, links, rechts
• Postorder-Durchlauf: links, rechts, anzeigen
• Levelorder-Durchlauf: schichtweise