# Prog 2
## Klessis Tipps
### ++Klausurrelevante Themengebiete++
- Interfaces (X)
- Generics (X)
- Dyn. Array
- Verkettete Liste, DVL
- Iterator (X)
- Abstrakte Datentypen (X), Laufzeitkomplexität (X) & Stapel
- Schlangen & Ringpuffer
- Comparator (X)
- Typeinschränkung
- binäre Suchbäume (X)
- Heap (X)

## Aggregation
Für die Klausuraufgabe 4 sehe ich gerade ist die Übungsaufgabe 8.2 ein gutes Training. Ist zwar Folge statt Stapel und Warteschlange, aber da müssen Sie auch statische generische Methoden schreiben, die einen ADT übergeben bekommen.

Folge und Menge sind nicht Klausur relevant

Genau, Sie müssen also keine Sortieralgorithmen auswendig können.

Aufgabe 2 kann Ringpuffer mit Implementierung sein. Und Iterator ist generell klausur-relevant. Also wäre auch die Implementierung eines Ringpuffer-Iterators denkbar.

Was ist hier die Frage? Aber generell dran denken dass bei A4 in der Klausur man keine ADT's und keine Datenstruktur selber programmieren muss, sondern alles schon gegeben ist. Wir arbeiten ja nur mit den Methoden des Interface vom jeweiligen ADT und müssen diese nur nutzen und nicht selbst implementieren.

Wir hatten in Kapitel 7 die Ringpuffer-Varianten FIFO ohne Überschreiben und LIFO mit Überschreiben kennengelernt. Aber das ist unabhängig voneinander. Es kann auch FIFO mit Überschreiben und LIFO ohne Überschreiben geben. Diese Varianten haben wir nur nicht betrachtet. FIFO/LIFO bezieht sich wie gesagt nur auf die get-Methode und mit/ohne Überschreiben bezieht sich nur auf die add-Methode.

Es gibt keine explizite Aufgabe dazu, aber eine Aufgabe kann das natürlich streifen. Insbesondere Aufgabe 4 in der Klausur ist ein guter Kandidat dafür. Sie sollten sich also mit Iterable, Iterator, Comparable und Comparator auskennen. Auch die forEach-Schleife sollten Sie beherrschen und wissen, wann man sie einsetzen kann/sollte und wann nicht.

Wichtig ist bei Generics zwischen Klassenmethode und Instanzmethoden zu unterscheiden. Das <T> im Klassenkopf bezieht sich nur auf die Instanzmethoden, dort kann man dann dieses T nutzen. Klassenmethoden sind aber völlig unabhängig und da ist das T dann nicht bekannt. Wenn Sie innerhalb einer Klassenmethode T nutzen wollen, dann muss dies wie gewohnt hinter dem Rückgabetyp mit <T> angezeigt werden. Dieses T ist dann unabhängig von dem <T> im Klassenkopf.
public class A<T> { // <- dieses T ist unabhängig vom T in der Klassenmethode
public static <T> void foo(DynArray<T> arr) {...}
}

Mit dem Heap (sowohl Min-Heap als auch Max-Heap) sollten Sie sich auskennen. Insbesondere einfügen und löschen im Heap mit upheap und downheap. Das auch wiederum grafisch als aufgezeichneter Baum und auch array-basiert. HeapSort und Prioritätswarteschlange sind nicht klausur-relevant.

Nur Typeinschränkung ist wichtig. Mit den Begriffen Kovarianz, Invarainz und Kontravarianz müssen Sie sich nicht auskennen.

Aufgabe 1
Die aus dem Semester relevanten Datenstrukturen sind:

DynArray
Ringpuffer
EVL
DVL
AVL-Baum
Heap

Mehr als das was in der Klausurvorschau steht, werde ich hierzu nicht verraten, da die Aufgabe sonst zu leicht wird:

Zeigen Sie, dass Sie wissen welche der grundlegenden Operationen der im Prog2-Verlauf behandelten Datenstrukturen welche Laufzeitkomplexität haben.
Diskutieren Sie auch, warum das so ist und wann man welche DS am besten einsetzt.

Aufgabe 2
Hier ist bewusst offen gehalten, ob es eine Theorie und/oder Implementierungsaufgabe ist. Es wird hier um DynArray und/oder Ringpuffer gehen.
Am besten für die Vorbereitung ist:

Falls Theorie: A 3.1 und A 7.2
Falls Implementierung: A 3.2 und A7.3

Da es vor kurzen auch gefragt wurde: Bei Implementierung und Ringpuffer müssten Sie auch mit Formeln der Art (p + size) % capacity umgehen können. Ja auch hier kann Iterator relevant werden.
Egal was es wird, worauf ich abziele steht in der Klausurvorschau ja schon genau drin:

Zeigen Sie, dass Sie sich damit auskennen, wie sich der interne Zustand einer array-basierte Datenstruktur bei den verschiedenen Operationen verändert.

Aufgabe 3
Im Grunde ist egal ob EVL und DVL. Bei DVL kommt eben die prev-Referenz hinzu, sonst das gleiche wie EVL.
Statt swap wird es in der Klausur eine andere neu ausgedachte Methode sein, die wir noch in nicht der Übung hatten.
Es wird in der Klausur eine Operation sein, bei der sich nur an einer Stelle in der verketteten Liste etwas ändert (also somit leichter als swap).
Bei swap bitte nicht nur die value's tauschen. Ich ziele darauf ab, dass Sie zeigen sollen, dass Sie das “Umhängen” von Referenzen in einer verketteten Liste beherrschen.
Beim Speicherbild genau aufpassen, dass Sie die Pfeile richtig zeichnen (siehe meine Lösung) und der Bezeichner immer ausserhalb eines Kästchens steht und der Wert innerhalb.
Aufgabe 4
Die konkrete Implementierung des ADT (Stapel und/oder Warteschlange) ist egal, da Sie nur die Methoden aus dem Interface des ADT nutzen können.
Zum Training eignet sich gut A8.2. Das ist zwar mit dem nicht klausur-relevanten ADT Folge, aber da müssen Sie auch generische Klassenmethoden schreiben, die einen ADT übergeben bekommen.
Ansonsten für Stapel die A6.2 und A6.4. Sowas wie A6.4 wäre natürlich für Klausur unter Zeitdruck zu schwer, aber ist ein super Training.
Für Warteschlange schau ich noch, ob mir da tatsächlich noch irgendeine Übungsaufgabe einfällt.
In Klausuraufgabe 4 kann natürlich auch Iterable, Iterator, Comparable und Comparator relevant werden und auch eine Typeinschränkungen <T extends ...> könnte mal an irgendeiner Stelle nötig sein.
Das Interface von Stapel und/oder Warteschlange wird vorgegeben sein, die Methoden müssen Sie nicht auswendig können.
Aufgabe 5
Theorieaufgabe wo AVL-Baum und Heap vorkommen kann und auch die allgemeinen Durchläufe bei binären Bäumen (preorder, inorder, postorder, Breitensuche) klausur-relevant sind.
Bei AVL-Baum muss man wissen, wie man einfügt und löscht und dabei entsprechend rotiert.
Beim Heap auch einfügen und löschen und wie man dabei entsprechend upheap und downheap macht. Bei Heap sollte man nicht nur grafisch Baum zeichnen, sondern auch Array-basiert fit sein.
Beim AVL-Baum gern die Doppelrotation ohne Zwischenschritt aufzeichnen. Wenn ungewollt ein Fehler gemacht wird, dann kriegt man mit Zwischenschritt aber leichter Teilpunkte.
Beim Löschen im AVL-Baum nicht vergessen, dass man eventuell mehr als einmal rotieren und weiter den Pfad bis zur Wurzel hin prüfen muss.

Also in diesem Fall des Ringpuffer müssen Sie ihn richtig verstanden haben, daher müssten Sie schon allein vom Verständnis her auf eine so geartete Formel kommen können. Also auswendig lernen hilft da nicht viel, da man ja oft entscheiden muss, ob noch irgendwo ein -1 oder ähnlichen rein muss in die Formel. Man muss es richtig verstanden haben, wie sich ein Ringpuffer intern verhält und z.B. auch wissen, warum man da modulo macht. Dadurch erreichen wir ja gerade dieses Ring-Verhalten des Arrays.

Wenn es um einen array-basierten Heap geht und sie sich das nicht anders merken können, an welchem Index das linke/rechte Kind und wo der Elternknoten im Array zu einem Knoten steht, dann wäre es gut die Formeln dazu zu kennen, also 2·p+1 usw.. Zur Not kann man sich das Heap-Array aber auch visuell als Baum aufzeichnen. Kostet dann aber natürlich mehr Zeit in der Klausur.

Ja immer null schreiben. Als Trick, damit man Zeit spart, würde ich x schreiben und irgendwo an der Seite noch x = null vermerken. Hauptsache Sie zeigen, dass Sie wissen, dass der Standardwert in einem Array vom generischen Typ null ist und nicht 0.

ier nun bei Bedarf noch ein Beispiel für eine Warteschlangen-Aufgabe (A4 in Klausur):

Schreiben Sie eine generische Java-Klassenmethode removeDuplicates, die eine Referenz auf eine Warteschlange als Parameter erhält und alle Duplikate aus der Warteschlange entfernt. Die Methode liefert eine neue Warteschlange zurück und die originale Warteschlange soll nicht verändert werden.

public static void main(String[] args) {
    Schlange<Integer> queue = new SchlangeEVL<>();
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(2);
    queue.enqueue(3);
    queue.enqueue(4);
    queue.enqueue(4);
    queue.enqueue(5);

    Schlange<Integer> result = removeDuplicates(queue);
    System.out.println("Original: " + queue);   // 1 2 2 3 4 4 5
    System.out.println("Ergebnis: " + result);  // 1 2 3 4 5 
}
    
/* Verwenden Sie folgende Definition des Interfaces: */
interface Schlange<T> extends Iterable<T> {
    int size();
    boolean isEmpty();
    T front();
    void enqueue(T e);
    void dequeue();
}

Es wird eine Methode sein die wir in der Übung noch nicht hatten und bei der sich die verkettete Liste nur an einer Stelle ändert, also insertAtPosition wäre ein Beispiel auf die das passt, aber updateAtPosition würde kein "Umhängen" von Referenzen erfordern und man brächte das betroffene Listenelement nur finden und den value aktualisieren.

Richtig, man kann/soll nur mit den Methoden des ADT arbeiten. Also in diesem Fall mit den Methoden des Schlange-Interfaces.

Würde DynArray benutzen wenns um Array Strukturen geht wo auch ein Index gefragt ist bzw. Daten hinzugefügt werden können oder entfernt (Verdoppeln und Halbieren).
Richtig, DynArray ist dann am besten, wenn man den get und set mit Index macht, also der Index bekannt ist und nicht erst gesucht werden muss.

EVL würde ich benutzen wenn oft was hinzugefügt oder gelöscht wird.
Wichtig ist explizit zu sagen, wenn vorne/hinten hinzugefügt/gelöscht wird und nicht in der Mitte, wo man die richtige Stelle erst suchen muss.

DVL würde ich über EVL benutzen wenn man öfter was löscht am Ende einer Liste bzw. > removeLast().
Richtig. Wenn man das prev bei DVL nicht ausnutzt, dann ist eine EVL auch besser, da man weniger Speicher verbraucht, weil man kein prev verwalten muss.

Ringpuffer würde ich benutzen wenn es um eine kontinuierliche Datenverarbeitung geht (Wartschlangen Prinzip, LiFo, FiFo) .
Würde eher sagen ein Ringpuffer macht immer dann Sinn, wenn Sie wissen, dass Sie genau maximal nur x Elemente haben (also Array fester Länge nutzen können) und typischerweise wenn es darum geht immer die letzten x Dinge haben zu wollen. Also die letzten x Temperaturwerte oder im Textprogramm die letzten x Änderungen per Undo rückgängig machen usw.. Je nach Anwendungsfall braucht man dann eine andere Ringpuffer-Variante. Da würde ich aber nicht in FIFO/LIFO denken, siehe hier: ⁠übung7⁠

AVL-Bäume würde ich benutzen, wenn viele Such-Einfüge und Löschoperationen erforderlich sind (Wegen O(logn)).
Wenn Sie oft in Werten mit einer inneren Ordnung nach bestimmten Werten suchen, da es contains mit O(log n) nur der AVL-Baum schafft.

Heap würde ich dann benutzen, wenn ich schnellstmöglich auf Max-Min Werte zugreifen möchte oder eine effiziente Sortierung durchnehmen will.
Ja das passt.

Genau, bei Heap auch das array-basierte nicht vergessen.

Hier müssten Sie vor dem routieren markieren, welcher Knoten die AVL-Bedingung verletzt und die andern beiden an der Rotation beteiligten Knoten. Dann erst kann ich sehen, ob Sie an der richtigen Stelle rotieren.

Darauf hatten wir glaub ich in den Übungen nie geachtet, aber sinnvoll wäre, dass der `Iterator` von `Schlange` gemäß FIFO erst das älteste, dann zweitälteste liefert und der `Stapel` gemäß LIFO erst das jüngste, dann zweitjüngste usw. liefert. Meine Implementierungen haben das aber auch nicht sehe ich gerade, da wird nur der `Iterator` der genutzten Datenstruktur (`DynArray`, `EVL`) zurückgegeben. In der Klausur kann man aber davon ausgehen, das `Stapel` und `Schlange` die Elemente gemäß LIFO und FIFO liefern. Natürlich nur, falls im Interface des ADT auch entsprechend `extends Iterable<T>` drin steht, sonst gibt es ja gar keinen Iterator.

Bei Aufgabe 4 müssen Sie beim gegebenen Interface genau hinschauen, ob extends Itarable<T> mit drin steht. Wenn das mit drin steht, dann können Sie vom ADT die iterator-Methode sich ein Iterator-Objekt geben lassen und mit dem dann mit while, hasNext und next alles durchgehen oder einfach die forEach-Schleife nutzen. Sie können davon ausgehen, dass das dann alles intern schon konkret implementiert ist und es einfach nur nutzen.

Bei einem Stapel können Sie nur auf das oberste Element zugreifen und push und pop machen. Alle Elemente eines Stapels durchzugehen, ohne den Stapel dabei zu verändern geht nur über den Iterator, sofern der Stapel Iterable ist. Gleiches gilt auch für die Warteschlange, wo Sie nur front, enqueue und dequeue zur Verfügung haben.

D.h. für Aufgabe 4 der klausur. Wenn das Intetface stapel extends Itarable ist. Dannn brauchen wir uns darüber keine Sorgen zu machen, ob mit DyAtray oder oder EVL implementiert ist. Wir gehen quasi davon aus, dass die in irgendeiner Form schon implementiert ist und wir können direkt auf die jeweiligen Methoden Next und hasNext zugreifen.

Ich habe ja schon so viel verraten, dass es bei A3 dann nicht swap, sondern eine andere Methode sein wird, bei der sich nur ein Element in der verketteten Liste ändert. Also zwei Listen aneinander zu ketten fällt damit raus.

Bei ADT's ist bei A4 in der Klausur, wie man ja auch in der Klausurvorschau sieht, das Interface mit angegeben. Sie sollen dann auch nur mit diesen Methoden arbeiten. Wenn Sie beispielsweise unbedingt eine contains haben wollen, dann müssten Sie die erst dazu implementieren.

Sie haben gesagt wir sollen uns die Aufgabe 3.2 und 7.3 genauer angucken falls es in der Aufgabe 2 der Klausur um Implementierung geht. In dem Fall sind es ja aber Aufgaben in denen die Datenstrukturen allgemein implementiert werden und nicht für ein bestimmtes Problem angepasst werden. Wäre es auch realistisch in der Klausur? Die Aufgabe 3.4 wäre doch zu lang für eine Klausuraufgabe oder? (Habe bisschen mehr als eine halbe Stunde gebraucht) Und die Aufgabe 7.4 ist ihrer (auch meiner) Meinung nach zu schwer für eine Klausuraufgabe.

Der beste Weg mit den internen Zuständen eines DynArray fit zu sein ist ja die Operationen selbst zu implementieren. Für eine Klausuraufgabe wäre das in der Tat zu viel, da würde man nur gezielt eine bestimmte DynArray-Methode oder ähnliches implementieren, aber jedenfalls nicht die komplette Datenstruktur.

Falls es bei A2 um Ringpuffer und Implementierung gehen wird, dann wird es drauf ankommen, dass Sie sich im Ringpuffer mit diesen Formeln der Form elements[(p + size) % capacity] auskennen. Also so eine Formel sollte Sie nicht abschrecken. Und natürlich nicht einfach auswendig lernen, sondern wirklich verstanden haben, damit Sie flexibel wissen, wann noch ein - 1 oder sonstiges erforderlich ist und was das modulo genau bewirkt und warum man das macht. Wie in der Klausurvorschau steht:
Zeigen Sie, dass Sie sich damit auskennen, wie sich der interne Zustand einer array-basierte Datenstruktur bei den verschiedenen Operationen verändert.
Der Iterator des Ringpuffers gehört da auch dazu.

Sie müssen das "umhängen" von Referenzen in einer verketteten Liste beherrschen. Das ist der Punkt, um den es geht. swap ist deshalb so schwer, weil sich da an zwei Stellen in der Liste etwas ändert. In der Klausur kommt dann eine andere Methode, bei der sich dann nur an einer Stelle in der Liste etwas ändern wird. Die Musterlösung zu verstehen bringt nicht so viel. Sie müssen es einmal konkret selbst gelöst haben und dann können Sie für die weitere Reflexion noch mit meiner Lösung abgleichen. Wem swap zu schwer ist, weil zu viel Sonderfälle sind, dann gern einfach eine andere Methode zum Training ausdenken, bei der sich nur an einer Stelle in der Liste etwas ändert. Wichtig ist, dass Sie nicht nur nachvollzogen und verstanden haben, sondern sowas selbstständig lösen können.

In der Klausur bei Aufgabe 2 kommt DynArray und/oder Ringpuffer. Wenn es Ringpuffer ist würde genau dabei stehen, was für ein Ringpuffer das ist. Also da würde dann genau dabei stehen, ob
add mit oder ohne überschreiben ist
get das jüngste oder älteste liefert
remove das jüngste oder älteste löscht.
Was den Iterator betrifft, würde auch nochmal explizit dabei stehen, ob der Iterator jüngste, zweitjüngste usw. oder älteste, zweitälteste usw. liefert.

In der Klausuraufgabe 4 verwenden Sie nur einen Stapel und/oder eine Warteschlange und müssen da keine Instanzmethode des ADT selbst implementieren. Es gibt nicht mehr zu wissen als das beim Stapel push was oben auf den Stapel legt und bei der Warteschlange enqueue etwas hinten an die Schlange anstellt.

Zur Sicherheit noch der Hinweis: Für die Klausur sind alle 3 Fälle beim Löschen im AVL-Baum relevant:
1.: zu löschender Knoten hat kein Kind
2.: zu löschender Knoten hat ein Kind
3.: zu löschender Knoten hat zwei Kinder
(Details siehe Folien)
Also auch das löschen mit 2 Kindern kann vorkommen, dann muss man sich dann für eine der beiden Möglichkeiten entscheiden, durch welchen Knoten man diesen ersetzt. Entweder der mit den nächst-kleineren oder den nächst-größeren Wert.

Iterable, Iterator, Comparable und Comparator sind alle klausur-relevant. Das diese auch Functional Interfaces sind, spielt da keine Rolle. Functional Interfaces sind mit Blick auf die Lambda-Audrücke nicht relevant, also Sie müssen nicht wissen, wie man diese Interfaces mit der ->-Notation nutzen kann. Functional Interfaces sind ja die Grundlage für Lambda-Ausdrücke, also diese ->-Schreibweise.

Die Frage ist etwas knapp formuliert. In Aufgabe 1 der Klausur sind alle behandelten Datenstrukturen relevant (DynArray, Ringpuffer, EVL, DVL, AVL-Baum und Heap) und es wird eine Theorieaufgabe sein, also da ist nichts zu implementieren. In Aufgabe 2 sind DynArray und Ringpuffer relevant, ob Theorie und/oder Implementierung ist offen gehalten. Falls Implementierung, müssen Sie nicht komplett DynArray oder Ringpuffer implementieren, das würde in der Klausur viel zu lange dauern (handschriftlich Code schreiben dauert ja besonders lange). Bei Aufgabe 3 ist nur EVL/DVL relevant. Bei Aufgabe 4 sind nur ADT Stapel und Warteschlange relevant. Mit welcher Datenstruktur die dann konkret zur Laufzeit realisiert sind, ist völlig irrelevant, da Sie ja nur die Interface-Methoden des ADT nutzen. Der Heap ist nur bei Augabe 1 und Aufgabe 5 relevant. Aufgabe 5 ist eine Theorieaufgabe, Sie müssen also nichts zum Thema Bäume in der Klausur implementieren. Ich hoffe ich habe das worauf Ihre Frage abzielt irgendwie getroffen.

Bei Aufgabe 4 gilt es eine generische Klassenmethode zu schreiben, die einen ADT übergeben bekommt. Mit welcher Datenstruktur der ADT dann konkret realisiert ist, entscheidet sich ja zur Laufzeit beim Aufruf dieser Methode. Wie man in der Klausurvorschau sieht, bekommen Sie ein Java-Programm (also eine main) vorgegeben, in der man beispielhaft sieht, wie die zu schreibende Methode genutzt wird. Welche Datenstruktur für den ADT genau genommen wird, entscheidet sich konkret in der Zeile ADT<...> adt = new ADTKonkret<>(); und die ist ja vorgegeben. Ob ADTKonkret dann was mit DynArray oder EVL oder sonstwas ist, spielt für die Lösung der Aufgabe keine Rolle. Der Compiler sieht ja nur den Typ des ADT's und Sie können nur die im Interface des ADT's enthaltenen Methoden nutzen. Sie können also ohnehin nichts DynArray- oder EVL-spezifisches aufrufen. Das ist ja der Vorteil von "Gegen das Interface implementieren", dass wir nur mit dem abstrakten Obertyp des Interface arbeiten und die konkrete Realisierung keine Rolle spielt.

Sie sollten die Heap-Operationen sowohl graphisch als auch in Array-Form beherrschen. Falls es in der Klausur array-basiert ist, können Sie sich ja bei Bedarf auf einem Hilfsblatt den Heap dazu auch graphisch aufmalen. Was im Array Vater oder linker/rechter Sohn ist, sollten Sie zuordnen können.

### ChatGPT
#### Version 1

Hier ist eine zusammengefasste Übersicht der wichtigsten Tipps für die Klausur:

### Allgemein:
- **Folge und Menge** sind nicht klausurrelevant.
- **Sortieralgorithmen** müssen nicht auswendig gelernt werden.
- Keine **ADTs** oder **Datenstrukturen** selbst implementieren – nur Methoden aus den Interfaces nutzen.

### Aufgabe 1:
- Relevante Datenstrukturen: **DynArray, Ringpuffer, EVL, DVL, AVL-Baum, Heap**.
- Wichtige Operationen: Laufzeitkomplexität der grundlegenden Operationen kennen und wissen, wann welche Datenstruktur am besten eingesetzt wird.

### Aufgabe 2:
- **DynArray und Ringpuffer** relevant.
- Für **Theorieaufgaben**: A 3.1 und A 7.2.
- Für **Implementierungsaufgaben**: A 3.2 und A 7.3.
- Ringpuffer: Formeln wie `(p + size) % capacity` verstehen und beherrschen.
- Fokus auf den internen Zustand der array-basierten Datenstrukturen bei verschiedenen Operationen.

### Aufgabe 3:
- Relevante Datenstrukturen: **EVL und DVL**.
- In der Klausur kommt eine Methode, bei der sich nur an einer Stelle in der verketteten Liste etwas ändert.
- Wichtig: **"Umhängen" von Referenzen** in einer verketteten Liste (nicht nur Werte tauschen).
- **Korrektes Zeichnen** der Referenzen im Speicherbild beachten.

### Aufgabe 4:
- Verwenden der Methoden aus dem Interface des ADT (Stapel und/oder Warteschlange).
- **Übungsaufgabe A8.2** als gutes Training.
- Keine Implementierung der Instanzmethoden des ADTs notwendig.
- Relevante Themen: **Iterable, Iterator, Comparable, Comparator**.
- **Type-Einschränkungen** (`<T extends ...>`) können relevant sein.
- Fokus auf generische Klassenmethoden, die einen ADT übergeben bekommen.

### Aufgabe 5:
- Theorieaufgabe mit **AVL-Baum und Heap**.
- Durchläufe bei binären Bäumen: **preorder, inorder, postorder, Breitensuche**.
- AVL-Baum: Einfügen und Löschen mit Rotationen (einschließlich Doppelrotation).
- Heap: Einfügen und Löschen mit **upheap und downheap**, sowohl grafisch als auch array-basiert.
- **Löschen im AVL-Baum**: Alle drei Fälle (kein Kind, ein Kind, zwei Kinder) sind relevant.

### Sonstige Hinweise:
- **Iterators** und **forEach-Schleife** nutzen.
- **Heap-Operationen** sowohl graphisch als auch array-basiert kennen.
- **DynArray** für array-basierte Strukturen nutzen, wo Index benötigt wird.
- **EVL** für häufiges Hinzufügen oder Entfernen an den Enden.
- **DVL** für häufiges Entfernen am Ende.
- **Ringpuffer** für kontinuierliche Datenverarbeitung und feste Kapazität.

### Beispiel für eine Warteschlangen-Aufgabe:

public static void main(String[] args) {
    Schlange<Integer> queue = new SchlangeEVL<>();
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(2);
    queue.enqueue(3);
    queue.enqueue(4);
    queue.enqueue(4);
    queue.enqueue(5);

    Schlange<Integer> result = removeDuplicates(queue);
    System.out.println("Original: " + queue);
    System.out.println("Ergebnis: " + result);
}

interface Schlange<T> extends Iterable<T> {
    int size();
    boolean isEmpty();
    T front();
    void enqueue(T e);
    void dequeue();
}

### Tipps für spezielle Aufgaben:
- **Ringpuffer-Formeln** verstehen, z.B. `(p + size) % capacity`.
- **AVL-Baum**: Doppelrotation ohne Zwischenschritt aufzeichnen.
- **Heap**: Formeln für Knotenpositionen im Array kennen (z.B., linker Sohn: `2*p + 1`).

Viel Erfolg bei der Klausur!

#### Version 2

Aufgabe 1:

Themen: Laufzeitkomplexität der grundlegenden Operationen der behandelten Datenstrukturen.
Relevante Datenstrukturen: DynArray, Ringpuffer, EVL, DVL, AVL-Baum, Heap.
Diskutieren Sie, warum die Laufzeitkomplexität so ist und wann welche Datenstruktur am besten eingesetzt wird.

Aufgabe 2:

Themen: DynArray und/oder Ringpuffer.
Zeigen Sie, wie sich der interne Zustand einer array-basierten Datenstruktur bei verschiedenen Operationen verändert.
Theorie und/oder Implementierung kann gefragt sein.
Vorbereitung: A 3.1, A 3.2, A 7.2, A 7.3.

Aufgabe 3:

Themen: Verkettete Listen (EVL und DVL).
Implementieren Sie eine Methode, die eine Änderung an der Liste vornimmt (z.B. swap(T a, T b) in der Klausurvorschau).
Zeichnen Sie Speicherbilder vor und nach der Operation.
Fokus auf das Umhängen von Referenzen in der verketteten Liste.

Aufgabe 4:

Themen: Arbeiten mit ADT (Stapel und/oder Warteschlange).
Implementieren Sie statische generische Methoden, die einen ADT übergeben bekommen.
Fokus auf Methoden des ADT-Interfaces und nicht auf eigene Implementierungen der Datenstruktur.
Mögliche Relevanz von Iterable, Iterator, Comparable, Comparator und Typeinschränkungen.

Aufgabe 5:

Themen: Theorie zu Bäumen (AVL-Baum, Heap).
Wissen über Einfügen und Löschen in AVL-Bäumen und Heaps.
Verständnis von Baum-Durchläufen (preorder, inorder, postorder, Breitensuche).
Keine Implementierung erforderlich, sondern theoretische Kenntnisse und grafische Darstellungen.

Generelle Hinweise:

Keine Sortieralgorithmen auswendig lernen.
Iteratoren und deren Implementierungen sind klausurrelevant.
Bei Generics zwischen Klassen- und Instanzmethoden unterscheiden.
Heap sowohl grafisch als Baum als auch array-basiert darstellen können.
Wildcards, JUnit, Lambda-Ausdrücke und Functional Interfaces sind nicht klausur-relevant.

### Gemini

Übungsaufgabe 8.2: Gutes Training für Klausuraufgabe 4, da statische generische Methoden mit ADT-Übergabe geübt werden.
Sortieralgorithmen: Nicht klausurrelevant.
Aufgabe 2: Ringpuffer mit Implementierung und Iterator möglich.
Aufgabe 4: Keine ADT- oder Datenstruktur-Implementierung nötig, nur Nutzung der Interface-Methoden.
Ringpuffer-Varianten: FIFO/LIFO und mit/ohne Überschreiben sind unabhängig voneinander.
Wichtige Konzepte: Iterable, Iterator, Comparable, Comparator, forEach-Schleife, Generics (Unterscheidung Klassen-/Instanzmethoden).
Heap: Min-Heap und Max-Heap, Einfügen und Löschen (upheap, downheap), grafische und array-basierte Darstellung. HeapSort und Prioritätswarteschlange nicht relevant.
Klausurrelevante Datenstrukturen: DynArray, Ringpuffer, EVL, DVL, AVL-Baum, Heap.

Aufgaben:

Aufgabe 1: Laufzeitkomplexität und Anwendungsfälle der Datenstrukturen.
Aufgabe 2: DynArray und/oder Ringpuffer (Theorie und/oder Implementierung). Formeln wie (p + size) % capacity verstehen.
Aufgabe 3: EVL/DVL, "Umhängen" von Referenzen in verketteter Liste beherrschen.
Aufgabe 4: Generische Klassenmethode mit ADT-Übergabe (Stapel und/oder Warteschlange). Iterable, Iterator, Comparable, Comparator und Typeinschränkungen können relevant sein.
Aufgabe 5: Theorieaufgabe zu AVL-Baum und Heap, allgemeine Durchläufe in binären Bäumen.

Zusätzliche Hinweise:

Ringpuffer: Formeln verstehen, nicht auswendig lernen.
Heap: Array-basierte Darstellung üben.
Verkettete Listen: "Umhängen" von Referenzen beherrschen.
Klausuraufgabe 4: Interface des ADT beachten (Iterable).
AVL-Baum: Alle drei Fälle beim Löschen relevant.
Generics: Lambda-Ausdrücke nicht relevant.
Datenstrukturen: In Aufgabe 1 alle relevant, in Aufgabe 2 DynArray und Ringpuffer, in Aufgabe 3 EVL/DVL, in Aufgabe 4 Stapel und Warteschlange, in Aufgabe 5 AVL-Baum und Heap (Theorie).

### Irrelevante Themen
- Functionale Interfaces
- Wildcards

## ++Interfaces++
Interfaces können Methoden Definitionen und Konstanten enthalten. Interfaces können von anderen (mehreren) Interfaces erben.
Interfaces mit nur einer Methode nennt man Functional Interfaces.

// A simple interface
interface Player extends Object2D
{
    final int id = 10;
    int move();
}

Klassen die Interfaces implementieren müssen alle Methoden enthalten, außer es handelt sich um eine abstrakte Klasse

public class MyElement implements Player {

    @Override
    public int move() {
        return 0;
    }

    @Override
    public int dimsension() {
        return 0;
    }
}

## ++Generics++

### Generische Klasse
Generische Klassen ermöglichen es, Klassen mit Typvariablen zu definieren, wodurch sie mit verschiedenen Datentypen verwendet werden können, ohne Code-Duplizierung oder Typunsicherheiten zu verursachen.

public class Paar<E, Z> {
    private E erstes;
    private Z zweites;

    public Paar(E erstes, Z zweites){
        this.erstes = erstes;
        this.zweites = zweites;
    }

    public E getErstes(){
        return this.erstes;
    }

    public Z getZweites(){
        return this.zweites;
    }

    public void setErstes(E erstes){
        this.erstes = erstes;
    }

    public void setZweites(Z zweites){
        this.zweites = zweites;
    }
}

### Generische Interfaces
Generische Interfaces ermöglichen es, Methoden mit Typvariablen zu definieren, die von den implementierenden Klassen spezifiziert werden können. Dadurch bleibt das Interface flexibel und anpassungsfähig für verschiedene Datentypen.

public interface Setzbar<T> {
    void set (T o);
    T get ();
    void reset ();
}

#### Generische implementierende Klasse
Eine generische implementierende Klasse verwendet die Typvariablen des Interfaces und implementiert die Methoden für einen spezifischen Datentyp, was die Wiederverwendbarkeit und Typensicherheit erhöht.

public class Kiste<T> implements Setzbar<T> {
    private T inhalt;

    @Override
    public void reset(){
        this.inhalt = null;
    }
}

#### Nicht-Generische implementierende Klasse
Eine nicht-generische implementierende Klasse gibt einen spezifischen Datentyp für das generische Interface an und implementiert die Methoden nur für diesen Typ, wodurch der Code spezifischer und oft einfacher wird.

public class Spieler implements Setzbar<String> {
    private String nickname;
    
    @Override
    public void set(String n){
        this.nickname = n;
    }
}

### Generische statische Methode
Generische statische Methoden ermöglichen es, Methoden mit Typvariablen zu definieren, die für verschiedene Datentypen verwendet werden können, ohne die Methode mehrfach definieren zu müssen.

static <T> T genericDisplay(T element)
{
    System.out.println(element.getClass().getName()
                       + " = " + element);
   return element;
}

### Generische Arrays
Generische Arrays können in Java nicht direkt erstellt werden, da dies zu Typunsicherheiten führen kann. Eine Möglichkeit, dies zu umgehen, ist die Verwendung eines Casts und die Erstellung eines Arrays von Object-Elementen.

T[] arr = (T[]) new Object[9];

### Typeinschränkung
Typeinschränkung garantiert das generische Typen bestimmte Eigenschaften haben, die für eine Klasse oder Methode wichtig sind.

public static <T> T minGen(T[] arr) {
    T m = arr[0];
    for (int i = 1; i < arr.length; i++){
        if(arr[i].compareTo(m) < 0){
            m = arr[i];
        }
    }
    return m;
}

Es müsste garantiert werden können:
- dass es für den Typ \<T> eine compareTo()-Methode gibt
- das heißt dass der Typ T das Interface Comparable\<T> implementiert
- das heißt, dass T ein **Untertyp** von Comparable\<T> ist

Genau das leistet **Typeinschränkung**

public static <T extends Comparable<T>> T minGen(T[] arr){
    T m = arr[0];
    for (int i = 1; i < arr.length; i++){
        if(arr[i].compareTo(m) < 0){
            m = arr[i];
        }
    }
    return m;
}

- Der Ausdruck **\<T extends Comparable\<T>>** schränkt die für T erlaubten Argumente ein
- auf Typen, die über eine compareTo()-Methode verfügen.

Es kann auch erforderlich sein, dass ein Typ T **mehrere** Bedingungen erfüllen muss, z.B.
- Unterklasse einer Klasse K zu sein
- ein Interface lfc1 zu implementieren
- ein Interface lfc2 zu implementieren

Die (nicht-generische) Klasse C würde diese Bedingungen erfüllen:

class C extends K implements lfc1, lfc2 {
    // CODE
}

**Generisch:** Forderung an das Typargument T:

class GenClass<T extends K & lfc1 lfc2> {
    // CODE
}

#### Wichtiges Beispiel (Suchbaum)

public class Suchbaum<T extends Comparable<? super T>> {
    // Class-Definiton
}

- T extends Comparable\<T>: Dies stellt sicher, dass T das Comparable\<T>-Interface implementiert. Das bedeutet, dass jedes Objekt vom Typ T in der Lage sein muss, mit einem anderen Objekt desselben Typs verglichen zu werden.
- \<? super T>: Dies erweitert die Flexibilität. Es bedeutet, dass T selbst oder jede Superklasse von T das Comparable-Interface implementieren kann. Das ermöglicht es Ihnen, Objekte vom Typ T nicht nur untereinander, sondern auch mit ihren Elternklassen zu vergleichen.

## Iterator
### Interface Iterator

public interface Iterator<E> {
    boolean hasNext();
    E next();
}

Das Iterator-Interface definiert zwei grundlegende Methoden:
- boolean **hasNext**(): Diese Methode gibt true zurück, wenn weitere Elemente in der Iteration vorhanden sind, und false, wenn keine weiteren Elemente mehr vorhanden sind.
- E **next**(): Diese Methode gibt das nächste Element in der Iteration zurück.

Durch eine implementierte Klasse (z.B. **class** MyIterator\<T> **implements** Iterator\<T>) kann man einen Durchlauf durch die Datensturktur folgendermaßen Implementieren:

Iterator<T> iterator = new MyIterator<>();
while(it.hasNext()){
    doSomething(it.next());
}

#### Beispiel einer benutzerdefinierten Iterator-Implementierung

import java.util.Iterator;

public class MyIterator<T> implements Iterator<T> {
    private T[] items;
    private int currentIndex = 0;

    public MyIterator(T[] items) {
        this.items = items;
    }

    @Override
    public boolean hasNext() {
        return currentIndex < items.length;
    }

    @Override
    public T next() {
        if (!hasNext()) {
            throw new java.util.NoSuchElementException();
        }
        return items[currentIndex++];
    }
    
    public static void main(String[] args) {
        Integer[] numbers = {1, 2, 3, 4, 5};
        MyIterator<Integer> myIterator = new MyIterator<>(numbers);
        
        while (myIterator.hasNext()) {
            System.out.println(myIterator.next());
        }
    }
}

### Interface Iterable

public interface Iterable<T> {
    Iterator<T> iterator();
}

Mit der Implementierung des Iterable-Interfaces können wir ohne Kenntnis der konkreten Impletierung über Datenstrukturen iterieren.

public class EVL<T> implements Iterable<T> {
    public Iterator<T> iterator() {
        return new EVLIterator();
    }
}

public class EVL<T> implements Iterable<T> {
    public Iterator<T> iterator() {
        return new Iterator(){
            @Override
            public boolean hasNext() {
                return currentItem.next != null;
            }

            @Override
            public T next() {
                if (!hasNext()) {
                    throw new java.util.NoSuchElementException();
                }
                currentItem = currentItem.next;
                return currentItem;
            }
        };
    }
}

### foreach-Schleife
Foreach-Schleifen sind besonders nützlich für die Iteration über Arrays und Sammlungen (wie Listen, Sets und andere Klassen, die Iterable implementieren), da sie eine einfachere und lesbare Syntax bieten als herkömmliche for-Schleifen.

for(T e : b){
    doSomething(e);
}

- Foreach-Schleifen können nicht direkt auf Datenstrukturen verwendet werden, die das Iterable-Interface nicht implementieren, wie z.B. herkömmliche Arrays in bestimmten Sprachen (außer sie werden speziell unterstützt wie in Java).
- Sie bieten keinen Zugriff auf den Index der Elemente, was in manchen Situationen nützlich sein kann, z.B. wenn Sie Elemente basierend auf ihrem Index ändern möchten.

> [!Note] Faustregel:
> Verwenden Sie die erweiterte for-Schleife bei Arrays nur dann, wenn nur lesend auf die Array-Elemente zugegriffen wird. Wenn Sie Elemente im Array ändern müssen, verwenden Sie eine herkömmliche for-Schleife mit einem Index.

#### Beispiel
##### Verwendung mit Arrays

int[] numbers = {1, 2, 3, 4, 5};
for (int number : numbers) {
    System.out.println(number);
}

##### Verwendung mit Listen

List<String> names = Arrays.asList("Alice", "Bob", "Charlie");
for (String name : names) {
    System.out.println(name);
}

## Schnittstelle Comparable\<T>
Mit Comperable zwingen wir dem Object eine Vergleichsmethode auf, mit der wir diese Objecte später vergleichen können.

public interface Comparable<T> {
    int compareTo(T var1);
}

Mittels dieser Methode kann "kleiner", "gleich" und "größer" für den Typ T definiert werden:

Der Aufruf 'a.compareTo(b);' liefet:
- einen **negativen** Wert, gdw. a "kleiner" als b ist.
- den int-Wert **0**, gdw. a "gleich" b ist.
- einen **positiven** Wert, gdw. a "größer" b ist.

> [!Warning]
> **Bedingung**:
> a.compareTo(b) == 0 $\iff$ a.equals(b);

Es ist **sicher zu stellen**, dass für alle $a, b, c \in T$ gilt:
- a.compareTo(b) < 0 $\iff$ b.compareTo(a) > 0
- (a.compareTo(b) < $\land$ b.comapreTo\(c) < 0) $\implies$ a.compareTo\(c) < 0
- a.compareTo(b) == 0 $\implies$ (a.compareTo\(c) < 0 $\iff$ b.comapreTo\(c) < 0)

### Beispiel

public class Stud implements Comperable<Stud> {
    private String name;
    private int matNr;
    
    @Override
    public int compareTo(Stud s){
    return this.matNr - s.matNr;
    }
}

## Schnittstelle Comparator\<T>

public interface Comparator<T> {
    int compare(T var1, T var2);
}

Die **compare(T a, T b)**-Methode liefert beim Aufruf:
- einen **negativen** Wert, gdw. a "kleiner" als b ist.
- den int-Wert **0**, gdw. a "gleich" b ist.
- einen **positiven** Wert, gdw. a "größer" b ist.

> [!Warning]
> **Bedingung** für **jeden** Comperator:
> a.compareTo(b) == 0 $\iff$ c.compare(a, b);

### Unterschied zur Schnittstelle Comparable\<T>
- Durch einen Komparator kann eine Klasse eine "**äußere Ordnung**" gegeben werden, auch wenn die Klasse keine "innere" Ordnung hat
- Eine Klasse mit innerer (natürlicher) Ordnung können weitere alternative Ordnungskriterien gegeben werden.

### Beispiel BubbleSort
#### Innere Ordnung
(denn Integer **implements** Comparable\<Integer>)

public static void bubbleSort(Integer[] a) {
    for(int n = a.length; n > 1; n--){
        for(int i = 0; i < n-1; n++){
            if(a[i].compareTo(a[i+1]) > 0)
                swap(a, i, i+1);
        }
    }
}

#### Äußere Orndung

public static <T> void bubbleSort(T[] a, Comparator<T> c) {
    for(int n = a.length; n > 1; n--){
        for(int i = 0; i < n-1; n++){
            if(c.compare(a[i], a[i+1]) > 0)
                swap(a, i, i+1);
        }
    }
}

public class NameComparator implements Comparator<Person> {
    @Override
    public int compare(Person o1, Person o2) {
        return o1.name().compareTo(o2.name());
    }
}

Person d = new Person("Denis");
Person a = new Person("Anna");
//...
Person[] p = {d, a, c, e, b};
bubbleSort(p, new NameComparator());

## ++Laufzeitkomplexität++
Gibt die Worst-Case-"Laufzeit" eines Algorithmus an.

Laufzeiten in aufsteigender Reihenfolge (best-to-worst):
- $O(1)$: konstante Laufzeit
- $O(\log(n))$: logarithmische Laufzeit
- $O(n)$: lineare Laufzeit
---
- $O(n^2)$: quadratische Laufzeit
- $O(2^n)$: ? Laufzeit
- $O(e^n)$: exponentielle Laufzeit

### Eigene Tablle
| Datenstruktur | Einfügen | Löschen | Suchen | Lesen |
| ------------- | ---------------------------------------------- | -------------- | -------------- | -------------- |
| EVL | O(1) mit last-Pointer o. vorne Einfügen / O(n) | O(n) | O(n) | O(n) |
| DVL | O(1) | O(n) | O(n) | O(n) |
| DynArray | O(n) | O(?) | O(n) | O(1) |
| Heap | O(log(n)) | O(log(n)) | O(n) | O(n) |
| Binbaum | O(n) | O(n) | O(n) | O(n) |
| AVL | O($\log(n)$) | O($\log(n)$) | O($\log(n)$) | O($\log(n)$) |
| Suchbaum | O($\log_2(n)$) | O($\log_2(n)$) | O($\log_2(n)$) | O($\log_2(n)$) |

### Übungstabelle
| Datenstruktur | T get(int pos) | void set(int pos, T value) | void add(T v) | boolean contains(T v) | void remove(int pos) | void delete(T v) |
| ---------------- | -------------- | -------------------------- | ------------- | --------------------- | -------------------- | ---------------- |
| AVL | - | - | O($\log(n)$) | O($\log(n)$) | - | O($\log(n)$) |
| Binärer Suchabum | - | - | O(n) | O(n) | - | O(n) |
| DynArray | O(1) | O(1) | O(n) | O(n) | O(n) | |
| EVL | O(n) | O(n) | O(1) | O(n) | O(n) | |

#### ++DynArray++
- int size():O(1)
- boolean isEmpty(): O(1)
- void set(int pos, T e): O(1)
- T get(int pos): O(1)
- void add(T e): O(n)
- String toString(): O(n)
- void increase(): O(n)
- void remove(): O(n)
- void remove(int pos): O(n)
- void delete(T e): O(n)
- boolean contains(T e): O(n)
- void decrease(): O(n)

#### ++EVL++
- int size(): O(1)
- boolean isEmpty(): O(1)
- T getFirst(): O(1)
- T getLast(): O(1) //mit Lastpointer?
- void insert(T e): O(1)
- void append(T e): O(1) // Im video nochmal nachhören mit Lastpointer?
- void removeFirst(): O(1)
- void removeLast(): O(n)
- void delete(T e): O(n)
- boolean contains(T e): O(n)

#### ++Ringpuffer++
- int size(): O(1)
- boolean isEmpty(): O(1)
- int capacity(): O(1)
- boolean contains(T e): O(n)
- T get(): O(1)
- void add(T e): O(1)
- void remove(): O(1)

#### ++DVL++
- int size(): O(1)
- boolean isEmpty(): O(1)
- T getFirst(): O(1)
- T getLast(): O(1)
- void insert(T e): O(1)
- void append(T e): O(1)
- void removeFirst(): O(1)
- void removeLast(): O(1)
- void delete(T e): O(n)
- boolean contains(T e): O(n)

#### ++AVL++
- void insert(T e): $O(\log(n))$
- void delete(T e): $O(\log(n))$
- boolean contains(T e): $O(\log(n))$
- T get(T v): $O(n)$

#### ++Heap++
- void insert(T e): $O(\log(n))$
- void delete(T e): $O(\log(n))$
- boolean contains(T e): $O(n)$
- T get(T v): $O(n)$
- T getMin()/T getMax(): O(1) / Min-Heap - Max-Heap

## ++Datenstrukturen++
Quelle: [Datenstrukturen W3Schools](https://www.w3schools.com/dsa/index.php)

### Unterschied ADT und DS
- Eine abstrakte Beschreibung von Anforderungen nennen wir ”Abstrakten Datentyp (ADT)“.
- Die konkreten Implementierungen bezeichnen wir als
”Datenstrukturen (DS)“.

Ein abstrakter Datentyp (ADT) und eine Datenstruktur sınd zwei miteinander verbundene Konzepte, aber sie sind nicht dasselbe:

#### Definition Abstrakter Datentyp (ADT):
* Ein abstrakter Datentyp ist eine mathematische Spezifikation eines Datentyps, die seine
möglichen Werte und die zulässigen Operationen auf diesen Werten definiert, ohne die
Implementierungsdetails anzugeben.
* ADTs defineren also nur, weiche Operationen möglich sind und welche Bedingungen dabei gelten
müssen, aber sie sagen nichts über die interne Struktur oder Implementierung dieser Operationen
aus
* ADTs kann als Schnittstelle betrachtet werden, die es erlaubt, mit einer bestimmten Art von Daten auf eine abstrakte Weise zu arbeiten.

#### Definition Datenstruktur (DS):
* Eine Datenstruktur ist dıe konkrete Impiementierung eines abstrakten Datentyps. See beschreibt.
wie die Daten tatsächlich organisiert und gespeichert werden, um die definierten Operationen
effizient ausführen zu können.
* Datenstrukturen bieten die konkreten Algorithmen und Datenorganısationen, um die spezifischen
Operationen des abstrakten Datentyps umzusetzen.
* Die Wahl einer bestimmten Datenstruktur hängt von den Anforderungen an Speicherplatz,
Zugriftszeiten und den zu erwartenden Operationen ab,

In einfacheren Worten ausgedruckt: Der abstrakte Datentyp definiert, was getan werden kann,
während die Datenstruktur definiert, wie es getan wird. Der ADT ist eine ideale Vorstellung davon, was
eine Datenstruktur tun soll, während die Datenstruktur die tatsächlche Implementierung ist, die diese
Idee ın die Praxıs umsetzt. s

### ++Abstrakte Datentypen (ADT)++
#### Stapel
Der Stapel arbeitet nach dem LIFO Prinzip. Last In - First Out
>[!Note]Definiert durch Methoden
>- **T top();** *Liefert das "oberste Element des Stapels"*
>- **void push (T);** *Legt ein neues Element auf den Stapel*
>- **void pop();** *Entfernt das oberste Element*

#### Schlange
>[!Note]Definiert durch Methoden
>- **T front ():** liefert das ”vorderste“ Element der Schlange
>- **void enqueue(T):** fugt ein neues Element in die Schlange ein
>- **void dequeue():** entfernt das vorderste Element

Wie beim Stapeln sind Duplikate erlaubt

#### Nicht Klausurrelevante ADT
##### Menge
##### Folge
##### Prioritätswarteschlange
---

### ++Datenstrukturen DS++
#### DynArray
>[!Note]Definiert durch Methoden
>

- int **size()**: liefert die Anzahl der gespeicherten Elemente
- boolean **isEmpty()**: liefert **TRUE** sollte kein Element gespeichert sein.
- **set(int pos, T v)**: überschreiben von bereits bestehenden Einträgen
- **T get(int pos)**: lesen eines bereits vorhandenen Elements
- void **add(T v)**: einfügen von Elementen: immer an der ersten unbegeleten Positon
- void **remove(int pos)**: Entfernt das Element an der Stelle *pos*
- void **delete(T v):** Entfernt den ersten Treffer vom Element **v**
- boolean **contains(T v):** Gibt **TRUE** zurück sollte das Element **v** im Array vorhanden sein.
- *private* void **increase()**: Falls die Kapazität (= Länge des Arrays) erschöpft ist, wird ein neues Array mit der doppelten Größe angelegt.
- *private* void **decrease()**: Reduziert die Größe des Arrays um die Hälfte, falls es nur noch um ein Viertel gefüllt sein sollte.
- *private* int **find(T v)**: Gibt die Position des Elementes **v** zurück.

Zugriff auf einer unbesetzten Position mit **set** und **get** liefert **IndexOutOfBoundsException**!


#### Ringpuffer
>[!Note]Definiert durch Methoden
> - int **size();** liefert die Anzahl der gespeicherten Elemente
> - boolean **isEmpty();** liefert **TRUE** sollte kein Element gespeichert sein.
> - int **capacity();** liefert die Anzahl an Speicherplätzen
> - boolean **contains(T v);** Gibt **TRUE** zurück sollte das Element **v** im Array vorhanden sein.
> - void **add(T e);** abhängig von Version MU $\iff$ OU
> - void **remove();** löschten den ältesten Eintrag zuerst.
> - T **get();** abhängig von Version MU $\iff$ OU
>
> **RingpufferOU\<T> "ohne Überschreiben"**
>- **add()** löst eine Exception aus und fügt nichts ein, falls der Puffer voll ist
>- **get()** liefert den ältesten gepufferten Wert
>- Der **Iterator** liefert die Elemente in der Reihenfolge ”ältester“, ”zweitältester“...
>
> **RingpufferMU\<T>** "mit Überschreiben"
>- **add()** überschreibt den ältesten Eintrag, falls der Puffer voll ist
>- **get()** liefert den jüngsten gepufferten Wert
>- der **Iterator** liefert die Elemente in der Reihenfolge ”jüngster“, ”zweitjüngster“...


#### EVL

>[!Warning] Der **Last**-Pointer muss nicht unbedingt exisitieren!

>[!Note]Definiert durch Methoden

- T **getFirst()**: Gibt den ersten Value in der verketteten Liste zurück.
- T **getLast()**: Gibt den letzten Value in der verketteten Liste zurück.
- void **insert(T v)**: Fügt das Element am Anfang der Liste ein (First zeigt auf das neue Element)
- void **append(T v)**: Fügt das Element am Ende der Liste ein (Last zeigt auf das neue Element)
- void **removeFirst():** Entfernt das erste Element
- void **removeLast():** Entfernt das letzte Element
- void **delete(T v)**: Entfernt das Element **v**
- boolean **containts(T v):** Gibt **TRUE** zurück sollte das Element **v** im Array vorhanden sein.

#### DVL
>[!Note]Definiert durch Methoden
- int **size();** liefert die Anzahl der gespeicherten Elemente
- boolean **isEmpty();** liefert **TRUE** sollte kein Element gespeichert sein.
- boolean **contains(T v);** Gibt **TRUE** zurück sollte das Element **v** im Array vorhanden sein.
- T **get(int i);** lesen eines bereits vorhandenen Elements
- void **set(int i,T v);**
- int **pos(T v);** gibt die Position des Elements v zurück
- void **insert(int i,T v);**
- void **addFirst(T v);** fügt das Element v vorne an
- void **addLast(T v);** fügt das Element v hinten an
- void **remove(int i);** löscht das Element an der Stelle i
- void **delete(T v);** löscht das Element mit dem Value v

#### Binbaum
>[!Note]Definiert durch Methoden

- Jeder Knoten hat **höchstens** zwei Kinder
- Die Kindern werden auch als "linkes Kind" oder "rechtes Kind" bezeichnet
- Die Knoten können auch einen "Inhalt" haben
- Knoten mit Kindern heißen auch **innere** Knoten
- Knoten ohne weitere Kinder heißen auch **Blätter**
- Eine Folge von Knoten von der Wurzel zu einem Blatt heißt Pfad.
- Ein Binärbaum der Höhe h enthält höchstens $2^{h+1}-1$ viele Knoten
- Ein Baum heißt **balanciert**, wenn isch in jedem Knoten die Höhe der Teilbäume um höchstens 1 unterscheidet.
- Ein **balancierter** Baum mit n Knoten hat eine Höhe von $O(log_2(n))$ $$h \in O(log_2(n))$$


- int **size();** liefert die Anzahl der gespeicherten Elemente
- boolean **isEmpty();** liefert **TRUE** sollte kein Element gespeichert sein.
- int **hoehe();** Liefert die größte Höhe. Die Höhe ist also gleich der Anzahl der Kanten eines längsten Pfad im Baum
- $h(b) = \begin{cases}
0 &\text{falls } b = \text{leer} \\
1 + max(h(t_l), h(t_r)) &\text{sonst}
\end{cases}$
- DynArray\<T> **inorder();** Liefert ein Dynamisches Array.

##### Depth First Search (DFS)
Ein Breitendurchlauf ("BFS - Breadth First Search") durch einen binären Baum liefert alle Knoten des Baums ebenenweise“ von links nach rechts.
Der BFS-Algorithmus startet mit dem Wurzelknoten und fpgt alle nicht-leerenKindknoten des aktuell besuchten Knotens in eine Schlange s ein. Das jeweils erste Element der schlange wird bearbeitet und danach aus der Schlange entfernt.

private class BfsIterator implements Iterator<T> {

    Schlange<Knoten> s = new SchlangeAlsDynArray<>();

    public BfsIterator(){
        if(root == null) {
            return;
        }
        this.s.enqueue(root);
    }

    @Override
    public boolean hasNext() {
        return !(s == null || s.isEmpty());
    }

    @Override
    public T next() {
        Knoten k = s.front();

        if(k.ltb != null){
            s.enqueue(k.ltb);
        }
        if(k.rtb != null){
            s.enqueue(k.rtb);
        }

        s.dequeue();
        return k.val;
    }
}

Als Pseudo-Code
- erzeuge eine Schlange s;
- falls Baum nicht leer
- füge root in s ein
- solange s nicht leer
- Knoten k = erstes Element aus s
- falls linker Sohn von k nicht leer
- füge linken Sohn in s ein
- falls rechter SOhn von k nicht leer
- füge rechten Sohn in s ein
- gibt k zurück (aus)
- entferne k aus s

###### Beispiel
Für den folgenden Baum liefert BFS die Knoten in der Reihenfolge:

**$$2 - 3 - 7 - 4 - 1 -8 - 6 - 5$$**

###### Pre-order Traversal
Zuerst der Wurzelknoten, dann (rekursiv) der linke
Teilbaum, dann (rekursiv) der rechte Teilbaum.


private void preOrderTraversal(T node){
    if(node != null){
        return;
    }
    System.out.print(node.data + ", ");
    preOrderTraversal(node.left);
    preOrderTraversal(node.right);
}

###### In-order Traversal
Zuerst (rekursiv) der linke Teilbaum, dann die Wurzel, dann
(rekursiv) der rechte Teilbaum.


private void inOrderTraversal(T node){
    if(node != null){
        return;
    }
    
    inOrderTraversal(node.left);
    System.out.print(node.data + ", ");
    inOrderTraversal(node.right);
}

###### Post-order Traversal
Zuerst (rekursiv) der linke Teilbaum, dann (rekursiv) der
rechte Teilbaum, zuletzt die Wurzel.


private void postOrderTraversal(T node){
    if(node != null){
        return;
    }
    
    postOrderTraversal(node.left);
    postOrderTraversal(node.right);
    System.out.print(node.data + ", ");
}

#### Suchbaum


- Vorraussetzung:
- Die Knoteneinträge sind von einem Datentyp, der Comparable implementiert
- Der Baum enthält keine Duplikate
- Mit den Operationen get(), contains(), insert(), delete() können Binäre Suchbäume also zu Darstellung von Mengen genutzt werden

##### Contains
1. Start at the root node.
2. If this is the value we are looking for, return.
3. If the value we are looking for is higher, continue searching in the right subtree.
4. If the value we are looking for is lower, continue searching in the left subtree.
5. If the subtree we want to search does not exist, depending on the programming language, return None, or NULL, or something similar, to indicate that the value is not inside the BST.


##### Insert Node
1. Start at the root node.
2. Compare each node:
- Is the value lower? Go left.
- Is the value higher? Go right.
3. Continue to compare nodes with the new value until there is no right or left to compare with. That is where the new node is inserted.


##### Find lowest Value
1. Start at the root node of the subtree.
2. Go left as far as possible.
3. The node you end up in is the node with the lowest value in that BST subtree.


##### Delete Node
1. If the node is a leaf node, remove it by removing the link to it.

2. If the node only has one child node, connect the parent node of the node you want to remove to that child node.

3. If the node has both right and left child nodes: Find the node's in-order successor, change values with that node, then delete it.

#### AVL-Baum
>[!Note]Definiton
>Ein binärer Suchbaum heißt AVL-Bau, wenn für jeden Knoten gilt:
>$$|h(k.ltb) - h(k.rtb)| \leq 1 $$
>Das heißt die höhe der Teilbäume untescheidet sich um nicht mehr als 1 (Balanciert)
>Für einen AVL-Baum T mit n Knoten gilt:
>$$h(T)\leq 1.5 * \log_2(n+1.5) \in \mathcal{O}(\log(n))$$
Anzahl der Knoten: $2^{h+1}-1$
##### Rebalancierung
>[!Note]Beobachtung
>Wenn in einem Knoten w die Balance gestört ist, dann hat der Teilbaum T (w ) mindestens die Höhe 2 und dann sind an der Verletzung immer ein Kind v und ein Enkel u von w beteiligt.
>Die drei beteiligten Knoten u, v , w haben immer insgesamt vier Teilbäume $T_1, T_2, T_3, T_4$ (die ggf. leer sein können).

>[!Note]Vier Fälle
>1. $u \leq v \leq w$
>2. $v \leq u \leq w$
>3. $w \leq u \leq v$
>4. $w \leq v \leq u$
>
>In allen 4 Fällen seien die Teilbäume so nummeriert, dass für alle Knoten
>$$p\in T_1, q \in T_2, r \in T3, s \in T_4$$
>$$p.val \leq q.val \leq r.val \leq s.val$$
>Kurz: $$T_1 \leq T_2 \leq T_3 \leq T_4$$

#### ++Fälle in denen eine Rebalancierung notwendig/geprüft werden muss++
- nach Insert
- nach Delete

##### ++1.Fall++ $u \leq v \leq w$
- Führe eine Rechts Rotation aus, um Balance wieder herzustellen
- Anschließend hat der Baum eine um 1 geringere Höhe als der Rotation

##### ++2.Fall++ $v \leq u \leq w$
- Führe eine Dopple-Rotation Links Rechts aus, um Balance wieder herzustellen

##### ++3.Fall++ $w \leq u \leq v$
- Führe eine Doppel-Rotation Rechts-Links aus, um Balance wieder herzustellen.

##### ++4.Fall++ $w \leq v \leq u$
- Führe eine Links-Rotation aus, um Balance wieder herzustellen.

#### Heap
>[!Note]Definition Datenstruktur Heap
>Ein Min- oder Max- Heap ist eine Datenstrukutr zur Darstellung
> - von partiell geordneten Bäumen
> - die links-vollständig sind
> - alle Ebenen bis auf die letzte voll besetzt und in der letzten Ebene so weit links wie möglich sitzen.
> - Die Höhe eines links-vollständigen Baums mit n Knoten ist in $\mathcal{O}(\log n)$
- Links-vollständige Bäume lassen sich leicht in einem Array implementieren, denn die Array-Indizes der Söhne bzw des Vaters eines Knoten lassen sich leicht aus dem Index des Knotens selbst berechnen:
- Wenn die Knoten eines links-vollständigen Baums in ”BFS-Reihenfolge“ in ein Array a eingefügt werden, dann gilt:
- $a[0] = root$
- für einen Knoten $k = a[p]$ an der Position $p$ gilt:
- die Position des **Vaters** von $k = (p − 1)/2$
- die Position des **linken Sohns** von $k = 2 · p + 1$
- die Position des **rechten Sohns** von $k = 2 · (p + 1)$

>[!Note]Definition Heap Eigenschaft
>- ++**MinHeap**++
> - Der Wurzeknotenwert ist das ++Minimum++ der Werte aller Knotenwerte.
>- ++**MaxHeap**++
> - Der Wurzelknotenwert ist das ++Maximum++ der Werter aller Knotenwerte.

#### Einfügen in einen Heap: upheap
- Methode ```void insert(T v):```
- Füge den neuen Wert k.val in einem neuen Knoten k an der nächsten freien Position des Baums ein. ($\leadsto Links-Vollständigkeit$)
- Stelle durch "upheap-Operation" die Heap Eigenschaft wieder her:
- sei f der Vaterknoten von k (sofern $k \neq root$)
- solange ($k! = root \space\space k.val < f.val$)(bei **MinHeap**)
- solange ($k! = root \space\space k.val > f.val$)(bei **MaxHeap**)
- vertausche k mit seinem Vaterknoten
- 

#### Entfernen aus einem Heap: downheap
- Methode ``` T remove():```
- Speichere den Wurzelwert für die spätere Rückgabe des Wertes
- Entferne den "letzten" Knoten des Baumes (in der untersten Ebene der am weitesten rechts stehende Knoten) und setze ihn an die Stelle der Wurzel. ($\leadsto Links-Vollständigkeit$)
- Stelle durch "downheap-Operation" die Heap-Eigenschaften wieder her:
- MinHeap:
- Solange ($k.val > k.lbt.val \space\space oder \space\space k.val > k.rtb.val$)
- vertausche k mit dem kleineren seiner Söhne
- MaxHeap
- Solange ($k.val < k.lbt.val \space\space oder \space\space k.val < k.rtb.val$)
- vertausche k mit dem größeren seiner Söhne

---
## Lösungen zur Klausurvorschau
### Aufgabe 1 (20 Punkte)
> **Beschreibung aus Klausurvorschau:**
> *Aufgabe zum Thema Laufzeitkomplexität. Zeigen Sie, dass Sie wissen welche der grundlegenden
Operationen der im Prog2-Verlauf behandelten Datenstrukturen welche Laufzeitkomplexität haben.
Diskutieren Sie auch, warum das so ist und wann man welche DS am besten einsetzt.*

**siehe Laufzeit**

### Aufgabe 2 (20 Punkte)
> **Beschreibung aus Klausurvorschau:**
> *Aufgabe zum Thema array-basierte Datenstrukturen, z.B. DynArray oder Ringpuffer. Zeigen Sie, dass
Sie sich damit auskennen, wie sich der interne Zustand einer array-basierte Datenstruktur bei den
verschiedenen Operationen verändert.*

DynArray,
Ringpuffer,
Noch mehr?

Beispielsweise: U07A2 (Tabelle)



### Aufgabe 3 (30 Punkte)
> Codevorgabe 3a

public class Main {
    public static void main(String[] args) {
        DVL<Integer> dvl = new DVL<>();
        dvl.append(1); dvl.append(2); dvl.append(3); dvl.append(4);
        // Vorher
        dvl.removeFirst(); dvl.swap(2,3); dvl.delete(2);
        // Nachher
    }
}


### Aufgabe 4 (25 Punkte)
(Datenschlange, Stapel oder weitere **Hilfsstrukturen**, Sternaufgabe, Stack sotieren (zu schwer für die Klausur), )
Keine gute Übung zur Warteschlange

Warteschlange / Stapel am wahrscheinlichstem

### Aufgabe 5 (25 Punkte)
Breitensuche, AVL-Bau, (Rotierung), Up-Heap, Down-Heap, Arraybasierter Heap,