Löst Problemklasse (Parameter)
Beschreibung endlich
(muss)
Resourcen endlich
(muss)
Laufzeit endlich
Gleiche Bedingungen ⇒ Gleicher Ablauf
(Gegenteil ist theoretisches Konstrukt)
Gleiche Bedingungen ⇒ Gleiches Ergebniss
(Komplexität)
Elementaroperationen pro Eingabegröße
AVL wenn:
$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
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
Wenn Blatt voll ⇒ Teilen
(Aus den Wiki commons)
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
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:
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.
Verschiedene Hashfunktionen der reihe nach durchprobieren bis eine eine freie stelle findet.
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).