Abstrakter Datentyp Queue und Tree Flashcards
(38 cards)
Warum sagt man, eine Schlange arbeitet nach dem FIFO-Prinzip?
Weil neu hinzugefügte Elemente Nachfolger vom letzt hinzugefügten Element sind. Der Head bleibt solange auf dem ältesten Element, bis dieses Dequed wird. Dann wandert der Head auf das nächst älteste Element.
Nenne die Methoden einer Schlange
empty
enque
front
deque
Nenne die Methoden einer Schlange
empty
enque
front
deque
Schreibe wie ich eine generische Klasse Box deklariere
public class Box <T>{</T>
Beschrifte einen Baum, welche Bestandteile hat er?
Im Grunde ist der Baum eine Verkettung von Knoten.
Der Quellknoten ist der Wurzelknoten. Ein Knoten besteht aus zwei Zeigerattributen links, rechts, diese zeigen auf den nächsten Knoten, und einem Inhaltattribut.
Nenne die Methoden eines Baumes
boolean empty()
Baum left()
Baum right()
Object value()
Was kann ein Knoten alles sein?
Der Wurzelknoten des gesamten Baumes
Der Wurzelknoten eines Teilbaums
Wenn der Knoten links und rechts null hat, also keine Kinder, dann ist er ein Blatt(leaf)
Nenne die drei Traversierungsarten für einen Baum
Inorder- Traversierung
Preorder-Traversierung
Postorder-Traversierung
Was ist die Traversierung eines binären Baumes?
Das systematische besuchen aller Knoten in einer bestimmten Reihenfolge
Wie funktioniert die Inorder-Traversierung?
Reihenfolge LVR
Er geht immer soweit wie es geht in die Tiefe, um links zu erreichen. Siehe Bild:
https://i.imgur.com/FcHS9Z9.png
Wie funktioniert die Preorder-Traversierung?
Reihenfolge VLR
https://i.imgur.com/mSZPbmg.png
Wie funktioniert die Postorder-Traversierung?
Reihenfolge LRV
https://i.imgur.com/IcCURwJ.png
Erkläre wie die Tiefensuche bei einem binären Baum funktioniert
Man geht links vor rechts in die Tiefe.
Wenn man ganz unten angekommen ist, geht man den nächsten Pfad der rechtsabgeht wieder links vor rechts in die Tiefe.
https://i.imgur.com/Kel3XWD.png
Erkläre die Breitensuche im binären Baum
Man fängt oben an der Wurzel an zu zählen und dann Ebene für Ebene von oben links nach unten rechts
https://i.imgur.com/9yZ3DYu.png
Erkläre wie der Rekrusive anzahlKnoten(Baum b) funktioniert
Der Algorithmus fängt bei der Wurzel an. Hier ist der Zähler bereits bei 1. Jetzt ruft sich die Methode rekursiv aber mit linker und rechter tochter auf. Sollte mind. eins existieren, steigt der Zähler wieder um +1.
Solange bis keine Tochter mehr da empty(), dann return 0.
Code:
public static int anzahlKnoten(Baum b){
if(b.empty()) return 0;
else return 1 + anzahlKnoten(b.left) + Anzahl Knoten(b.right());
}
Was ist ein Suchbaum
Ein binärer Baum, bei dem alle Einträge des Teilbaums links vom Knoten x kleiner sind, und rechts größer. https://i.imgur.com/aMov34R.png
Warum hat man Suchbäume entwickelt?
Eine sehr effiziente Datenstruktur, mit der Lookup, insert und delete sehr effizient geht.
Wie ist die Komplexität des Suchbaums. Nenne Best case, Worst case & Average case
BestCase (Jeder Knoten hat zwei Töchter) ausgenommen Blätter (leaf)
h = log(n) Wegknoten
h == höhe
n == Anzahl der Knoten
Worst Case: Elemente untereinander eingegeben
Der Baum wird zur Liste…
Aufwand 0(n)
Average case: O(log(n))
Was ist ein AVL-Baum?
Ein ausgeglichener binärer Suchbaum. Das bedeutet: Die Höhen der Töchterknoten unterscheiden sich maximal um 1.
Ein unausgeglichener Baum hat irgendwo einen Knoten, der unausbalancierte Kinder hat.
Nenne die Bezeichnungen, um die Position dieses unausgeglichenen Knotens zu finden.
Man unterscheidet zwischen vier Fällen. Man guckt an welcher Position ausgehend von der Wurzel, der unausgeglichene Knoten hinzugefügt wurde.
LL == Linker Teilbaum Linkes Kind
RR == Rechter Teilbaum Rechtes kind
LR == Linker Teilbaum Rechtes Kind
RL == Rechter Teilbaum Linkes Kind
Unbalancierte Wurzel LL, welche Rotation macht man?
Eine Rechtsrotation, sodass die Wurzel des Fehlerhaften Teilbaums nun die Wurzel des gesamten Baumes ist.
Unbalancierte Wurzel RR, welche Rotation macht man?
Eine Linksrotation, sodass die Wurzel des Fehlerhaften Teilbaums nun die Wurzel des gesamten Baumes ist.
Unbalancierte Wurzel LR, welche Rotation macht man?
Eine Doppelrotation, sodass der Vater des Fehlerhaften Elements nun die Wurzel des gesamten Baumes ist.
Das Fehlerhafte Element wird dann korrekt einsortiert.
Unbalancierte Wurzel RL, welche Rotation macht man?
Eine Doppelrotation, sodass der Vater des Fehlerhaften Elements nun die Wurzel des gesamten Baumes ist.
Das Fehlerhafte Element wird dann korrekt einsortiert.
