====== AlgoDat ======
===== Algorithmus =====
==== Definition ====
  * präzise
  * endlich
  * Elementaroperation
  * Ausführungsorgan
  * Abbildung

==== Eigenschaften ====
=== Abstrahierung/abstrakt ===
Löst Problemklasse (Parameter)

=== Statische Finitheit/statisch finit ===
Beschreibung endlich \\
(muss)

=== Dynamische Finitheit/dynamisch finit ===
Resourcen endlich \\
(muss)

=== Terminierung/terminiert ===
Laufzeit endlich

=== Determinismus/deterministisch ===
Gleiche Bedingungen => Gleicher Ablauf \\
(Gegenteil ist theoretisches Konstrukt)

=== Determiniertheit/determiniert ===
Gleiche Bedingungen => Gleiches Ergebniss 
  * terminiert + deterministisch => determiniertheit
  * terminiert + nicht deterministisch => determiniertheit oder nicht determinierend

===== Effizienz =====
(Komplexität)
  * Laufzeit
  * Resourcen

===== Laufzeitanalyse =====
Elementaroperationen pro Eingabegröße

===== Bäume =====
==== AVL-Bäume ====
AVL wenn:
  * Binär
  * $bal(T) \in \{-1, 0, 1\}$ 

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

{{http://upload.wikimedia.org/wikipedia/commons/thumb/f/f5/AVL_Tree_Rebalancing.svg/350px-AVL_Tree_Rebalancing.svg.png}} \\
(Von [[http://en.wikipedia.org/wiki/File:AVL_Tree_Rebalancing.svg|wiki]])

Ein [[http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html|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


^    Ebene n |         -2       |||         +2       ||| |
^  Ebene n+1 |  Linke Seite     ||| Rechte Seite     ||| (Diese seite muss existieren, da sie ja auch die schwerere ist)  |
^   :::      |  -1  |   0  |  +1  |  -1  |   0  |  +1  |
^     Aktion |  Einfach  |  Einfach  |  Doppelt  |  Doppelt  |  Einfach  |  Einfach  | |
|  |||  Unterschiedliche Vorzeichen \\ => Doppelrotation  ||  || |

**Nach den Regeln im Script rotieren**

==== B-Baum ====
=== Einfügen ===
  * 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

{{http://upload.wikimedia.org/wikipedia/commons/5/58/B-tree-splitt.png?500}}\\
(Aus den [[http://de.wikipedia.org/w/index.php?title=Datei:B-tree-splitt.png&filetimestamp=20050729184549|Wiki commons]])

==== B* ====
m ist ein vielfaches von 3

{{:users:skruppy:ext:uni:2:b-ov1.png?400|}}

{{:users:skruppy:ext:uni:2:b-ov2.png?500|}}
==== Optimaler B-Baum ====
{{:users:skruppy:ext:uni:2:opt-bin-tree.png?450|}}

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.
===== Hash =====
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:
  * //Sur//jektivitä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, ...
==== Divisionsmethode b=1 ====
k mod m mit m prim und m > 2 sonst keine Randomisierung.

- Aufeinanderfolgende Schlüssel => Aufeinanderfolgende Adressen

==== Middle-Square-Methode b=1 ====
k² und x ziffern aus der mitte des Ergebnisses rausziehen.

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

==== Kolisionsstrategie ====
=== Offenes Hashverfahren ===
Ein extra heap um daten zu speichern. Hashtable nur als einstiegspunkt in andere Datenstrukturen.
== Direkte Verkettung ==
Jede adresse = Linked list

=== Geschlossene Hashverfahren ===
Alle Daten werden nur in der hash table gespeichert.
== Direkte Verkettung mit Verschmelzen ==
  * 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.
== Offene Addressierung (rehashing) ==
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

==== foo ====
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).