AlgoDat

• präzise
• endlich
• Elementaroperation
• Ausführungsorgan
• Abbildung

Löst Problemklasse (Parameter)

Beschreibung endlich
(muss)

Resourcen endlich
(muss)

Laufzeit endlich

Gleiche Bedingungen ⇒ Gleicher Ablauf
(Gegenteil ist theoretisches Konstrukt)

Gleiche Bedingungen ⇒ Gleiches Ergebniss

• terminiert + deterministisch ⇒ determiniertheit
• terminiert + nicht deterministisch ⇒ determiniertheit oder nicht determinierend

(Komplexität)

• Laufzeit
• Resourcen

Elementaroperationen pro Eingabegröße

AVL wenn:

• Binär
• $bal(T) \in \{-1, 0, 1\}$

$bal(t) = H(t_r) - H(t_l)$ (Rechts vor links)

(Von wiki)

Ein C++ code sagt mehr als tausend Worte.

http://209.237.84.181:7600/index.php/AVL_Trees

http://webdiis.unizar.es/asignaturas/EDA/AVLTree/avltree.html

Nach den Regeln im Script rotieren

• Auf unterster Ebene.

Wenn Blatt voll ⇒ Teilen

• größe $n \cdot 2+1$ mit neuem Element ⇒ Es gibt ein mittleres Element
• Mittleres Element bei parent inserten
  • an der Stelle wo der link nach unten ging
  • alter link löschen
  • neue links zum mittleren Element zum linken/rechten neuen Blatt
  • ggf. parent teilen

(Aus den Wiki commons)

m ist ein vielfaches von 3

In diesem Beispiel ist das Gewicht des BAuemes 48 (nicht zwangsweise optimal)

http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module9/module9.html

http://de.wikipedia.org/wiki/Bellman-Algorithmus

http://de.wikipedia.org/wiki/Gewichteter_bin%C3%A4rer_Suchbaum

• Von unten nach oben zusamenbauen
• Ein Baum aus einem element ist bereiz optimal
• Beim zusammenschlus zweier knoten muss der root so ausprobiert werden das der neue auch wieder optimal ist.

NEU

Monotonieverhalten: Werden zwei Bäume gemerged und sie haben die selbe wurzel, so ist sie auch die Wurzel der vereinigung.

Die Wurzel de gemergen liegt zwischen den Wurzeln der teilbäume (inklusiv ihnen).

Angeblich kann man bei Optimalen Binärbäumen mit warscheinlichkeiten für erfolglose suchen nicht so einfach addieren … nochmal in der VL nachschauen.

Schlüssel/key – Hash Funktion –> Addresse (m-Stück)

Kardinalität: card(K) = Anzahl möglicher Schlüssel

Addresse = Bucket addresse

Es gibt m buckets

Ein bucket kann b Schlüssel fassen

Perfektes hashing = eine addresse nicht mehr als b mal.

Erwünschte eigenschaften:

• Surjektivität: Jede speicherzelle soll verwendet werden
• Gleichmäsige verteilung
• Effiziente berechnung
• Randomisierung: Nichtzufällige Schlüssel –> Zufällige Addressen

ORD(c) für Zeichen: a=1, b=2, …

k mod m mit m prim und m > 2 sonst keine Randomisierung.

- Aufeinanderfolgende Schlüssel ⇒ Aufeinanderfolgende Adressen

k² und x ziffern aus der mitte des Ergebnisses rausziehen.

- 0-Blöcke am anfang oder am ende ⇒ Nicht gleichmäsig verteilt

Ein extra heap um daten zu speichern. Hashtable nur als einstiegspunkt in andere Datenstrukturen.

Jede adresse = Linked list

Alle Daten werden nur in der hash table gespeichert.

• Linked list in der hash table.
• Nächstes freies feld vom ende suchen.
• Wenn „mein“ feld bereits mit nachvolger eines anderen hashes belegt … egal hänge dich an das ende seiner liste.

Verschiedene Hashfunktionen der reihe nach durchprobieren bis eine eine freie stelle findet.

• lineares sondieren: $h_i(k) = (h(k) + 1) \bmod m$
  • - Löschen nicht direkt möglich ⇒ „Gelöscht“ Markierung

http://www.dgp.toronto.edu/~jstewart/270/9798s/Laffra/DijkstraApplet.html

Übung 8, prüfen der split bedingung entweder nur nach dem einfügen oder so lange splitten bis es passt (ersteres ist einfacher).