Kapitel 5: Datenstruktur Baum Flashcards
Definition Baum
Ein Baum ist eine Datenstruktur, die aus einer Menge von Knoten besteht. Jeder Knoten kann auf andere Knoten über Kanten (Referenzen) verweisen.
Was charakterisiert den Wurzel-Knoten ?
Der Erste Knoten im Baum
Was charakterisiert einen Blatt-Knoten ?
Ein Knoten ohne Nachfolger
Was gibt es neben Wurzel- und Blatt-Knoten noch für Knoten in Bäumen ?
Innere Knoten
Definition Niveau eines Knotens
Das Niveau eines Knotens ist die Länge des Pfades von der Wurzel bis zu diesem Knoten.
Definition Höhe eines Knotens
Die Höhe eines Knotens ist die Anzahl der Kanten bis zum tiefsten Blatt.
Formel Höhe eines Knotens
max aus(höhe links, höhe rechts)+1
Welche Höhe haben Blattknoten ?
0
Welche Höhe hat eine nullptr Referenz ?
-1
Definition Pfad
Ein Pfad in einem Baum ist eine Folge von verschiedenen Knoten, in der die aufeinander folgenden Knoten durch Kanten miteinander verbunden sind.
Zwei Grundlegende Eigenschaften eines Baumes
- zyklenfrei
- zusammenhängend
Wie heißt ein Baum mit 3 Knoten zu jedem Knoten ?
Ternärer Baum
BST: Wo steht der größere Vergleichsschlüssel zu einem Knoten, Links oder Rechts ?
Rechts
Eigenschaften BST
- Jeder Knoten hat bis zu 2 Nachfolfger
- Geordneter Baum durch Vergleichsschlüssel
- Zyklenfrei
- Zusammenhängend
Wie bestimmt sich der Linke Nachfolger zu einem gegebenen Index i in einer dynamisch verketteten Datenstruktur ? (BST)
2 * i +1
