T&A AD Lernkarten

- schrittweises Verfahren
- ausführbare Schritte
- eindeutiger nächster Schritt (deterministisch)
- endet nach vielen Schritten (terministisch)

Konzept zur Speicherung und Organisation von Daten.

Struktur -> Anordnung zum Verwalten der Dateien
Operationen -> Ermöglichen Zugriff

(alg. Datenstruktur s9)

Resourcenbedarf = f(Eingabedaten)

Eingabedaten:
Datenmende
Datenwerte

Resourcen:
Rechenzeit - Zeitkomplexität
Speicherbedarf - Speicherkomplexität

O(1)
O(log(n))
O(n)
O(log(n) * n)
O(n^m)
O(d^n)
O(n!)

Nein - da konstante Faktoren wichtig werden
Langsame algorithmen könne io. sein

explizit / implizit - parent hat referenz / hat referenz
statisch / dynamisch - grösse on init / dynamische grösse
direkt / indirekt - zugriff direkt möglich / indirekt über refenzen

positiv
- mächtiges Lösungskonzept
- häufig einfache und elegante Lösung
- weniger Quellencode
- Korrektheit häufig einfacher nachweisbar
- spezielle Programmiersprachen: Lisp, Prolog

negativ:
- schnell viele methodenaufrufe
- tendenziell langsamer als iterativ - da viele methodenaufrufe
- grosser call-stack benötigt
- gefahr - stack overflow

- unsortiert - einfach einfügen
- Datenelemente behalten ihre Reihenfolge
- Datenstrukur ist immer sortiert

Basic:
Einfügen
Suchen
Ersetzen
Entfernen

Reihenfolge spezifisch:
Nachfolger
Vorgägner
Sortieren
Maximum / Minimum

einfügen:
unsoritert : O(1)
sortiert: O(log n) + O(n) => O(n)

Entfernen:
sortiert: O(log n) + O(n) => O(n)
unsortiert: O(n)

suche:
sortiert: O(log n)
unsortiert: O(n)

Eigenschaften:
statisch
explizit
direkt
Reihenfolge

Einfügen:
sortiert: O(log n)  (wenn skip-list) -> sonst O(n)
unsortiert: O(1)

entfernen:

sortiert: O(log n)  (wenn skip-list)
unsortiert: O(n) (suchen & entfernen -> indirekt)

Suche:

sortiert: O(log n) (wenn skip-list)
unsortiert: O(n) 
 

Eigenschaften:dynamisch
implizit
indirekt
Reihenfolge

Typen:
einfach (tale)
doppelt (tale + head)

push() - O(1)  / pop() - O(1)

Java-Imp.:
ArrayDeque
LinkedList
Deque

Array:
+ Platz reserviert
+ schnelles einfügen
- beschränkte grösse

List:
+ Leerer Stack sehr klein
+ dynamische Grösse
- etwas langsamer - da Speicher muss platz gemacht werden

offer() O(1) / poll() O(1)
enqueue / dequeue

Java-Implementationen
LinkedList
ArrayDeque
Deque<I>

List:
+ leere queue fast kein platz
+ dynamische grösse
- etwas längsämer - speicherreservation

Array:
+ maximaler Platz bereits reserviert
+ daher schnell
- statische Grösse

- Daten haben hirarchische Struktur
- Binärsuche mit O(log(n))

- Out-Tree - pfeile root ->
- In-Tree - pfeile -> root

- Binär-Baum - häufigsten
- AVL-Baum
- B-Baum
- B*-Baum
- Binominal-Baum

- Wurzel (Root)
- Knoten (Node)
- Blatt (Leafe)
- Kanten (Edge)

- Ordnung - max childs
- Grad - Anzahl childs - Knoten
- Pfad - weg von Knoten -> Wurzel
- Tiefe - Anzahl Knoten auf Pfad von Knoten (Wurzel = 1)
- Niveau - Ebene
- Höhe - Höhe des Baumes - Tiefe des weit entferntesten Knoten
- Gewicht - Anzahl Knoten

- ausgefüllt - alle inneren Knoten maximum an Kindern
- voll / ausgeglichen - alle niveaus voll ausser das letzte linksbündig
- vollständig / komplett - voller / symetrischer Baum

Preorder - Haupreihenfolge
Postorder - Nebenreihenfolge
Inorder - Symetrische Reihenfolge

- Suchen
- Einfügen
- Entfernen
- Balancieren
- Traversieren

- Blatt - just do it
- Knoten mit einem Blatt : Blatt -> Knoten
- Knoten mit zwei Blätter: Knoten mit weitesten linkes Blatt des rechten Teilbaumes austauschen (nächst grösserer Wert)

Speichergrösse zu Kollisions verminderung -> Konflikt

#Load-Faktor : Wie viel grösser ist die Datenstruktur als ihre Werte.

- Final / Finalisieren
- Unit-Testen / gut testen
- Gleichheit nur auf Schlüsselwerte vergleichen
- @Override - compiler hilft wenn fehlgetibt und co
- Equals by Objektreferenzen weiter delegieren

Eigenschaften:
- Keine Methoden die Daten mutieren
- final / keine spezialisierung der Klasse zulässig
- Attribute werden privat & final (nur beim erzeugen setzten)
- Exklusiver Zugriff
   - nur getter
   - keine mutierbaren referenzen ausserhalb

+ Thread safe ohne synchronisation
+ beliebig verteilbar - unproblematisch beim verwenden von Collections oder Datensharing
+ gut als Attributtypen bei komplexen strukturen

Einfach -> alles was man kann -> final
wenn get Funktion -> nur immutable Objekt oder eine kopie der referenz / instance
 

- Eclipse-Collections (kompakt & assagestarke API - wenig Speicher versprechen)
- HPPC (Grosse Set an elemtartypen
- google-guava (umfangreich)

Eher nicht: da

- abhängig
- zuerst Java-lib ansehen
- 3rd party-lib ausgiebig testen und vorteil aufzeigen
- wirklich nur bei special cases