Datenstrukturen & Algorithmen

Laufzeit: \(\mathcal{O(n^2)}\)

Laufzeit: \(\mathcal{O(n^2)}\)

Elternknoten in einem Heap müssen immer einen grösseren Wert haben als ihre Kinderknoten

Mit "Versickern" ist gemeint, dass das oberste Element mit dem grösseren  (direkten) Kindelement getauscht wird. Dies geschieht so lange, bis die Heap-Bedingungen im Heap wiederhergestellt wurden. 

Laufzeit: \(\mathcal{O(n*log(n))}\)

Laufzeit: \(\mathcal{O(log(n))}\)

Ähnlich Heap-Sort. Da sich ein Grossteil der Knoten auf dem untersten Niveau befinden macht es Sinn, den auf dem Versickerungspfad von "unten" an zu suchen.

Es findet ein grosses "Umherhüpfen" im Suchbaum statt. Dies kann je nach System sehr langsam werden, da das Zugreiffen auf nahe gelegene Speicheradressen billiger ist als der Zugriff auf entfernte. (Caching-Effekt)

Laufzeit: \(\mathcal{O(n*log(n))}\)

Achtung: Benötigt extra Speicherplatz von \(\mathcal{O(n)}\)

Auf dem Divide-And-Conquer-Prinzip

Laufzeit: Normalerweise/Durchschnittlich: \(\mathcal{O(n*log(n))}\)

Im schlechtesten Fall \(\mathcal{O(n^2)}\)(Tritt aber in der Praxis prakitsch nie ein-> Wenn der Pivot immer sehr schlecht ist. Es ist auch eine Möglichkeit 3 Elemente zu wählen und den Median dieser Elemente als Pivot zu nehmen.)

Bekanntlich nimmt ein Suchverfahren die beliebigen Werte \(a_1 a_2a_3....a_n\)  entgegen. Damit das Suchverfahren korrekt sein kann, muss es eine beliebige Permutation der Reihe ausspucken können. Es gibt daher n! mögliche Lösungen. 

Stellt man sich den Suchalgorithmus als Entscheidungsbaum vor, bei welchem man am Ende immer die Lösungspermutation kennen muss, so muss der Suchbaum n! Endknoten haben. Mittels Induktion kann bewiesen werden, dass der mittlere Suchweg \(log(n!)\) entspricht, was \(\in \Theta (n*log(n))\) ist. 

Beim Bucketsort werden die zu sortierenden Werte etwas näher betrachtet und auf "Eimer" verteilt. In einen Eimer kommen Zahlen mit passenden Eigenschaften, Beispielsweise diejenigen mit einem bestimmten 1000er Wert (4000, 4512, 4129 in den 4er Eimer, 8102 in den 8er Eimer usw.). Die Eimer werden dann mit einem simpleren Sortieralgorithmus sortiert und anschliessend wieder zusammengesetzt. 

Lineare Laufzeit, besonders hilfreich bei grossen Datenmengen. 

Beim Radix-Sort werden die Werte im Array jeweils Ziffer für Ziffer betrachtet und anschliessend auf 10 unterschiedliche Buckets verteilt. Wir beginnen mit der führenden Ziffer (09124 kommt in die 0;12913, 11291 in die 1 usw.). Wir sammeln die Zahlen in aufsteigender Reihenfolge wieder ein. Anschliessend wird nach der zweiten Zahl sortiert, wieder aufgesammelt usw. Solange, bis wir durch alle Ziffern durch sind.

Statt mit der führenden Ziffer kann man auch mit der letzten Ziffer beginnen. Sei m die Anzahl verschiedener Ziffern  (bei Zahlen 10), l die Anzahl Ziffern pro Wert und n die Anzahl Datensätze, so ist \(\mathcal{O((n+m)*l)}\)

Eine BEschreibung von Daten und den darauf anwendbaren Operationen (zB Einfügen, Löschen, Suchen). Die Implementierung eines abstraktesn Datentyps nennt man Datenstruktur. 

Die Effizienz sagt aus, wie es sich mit der Laufzeit einzelnder oder einer Folge von Operationen verhält. 

Als Array (Laufzeiten: Siehe Lernkarten zuvor...)

Lineare Liste (Laufzeiten: Linear)

Skip-Liste: (Liste die mittels zusätzlichen Zeigern das Suchen wie in einem Suchbaum ermöglicht. Löschen, Einfügen ist linear, suchen in log(n)). 

Suchbaum

-> Die Schlüssel im linken Teilbaum sind immer kleiner als die Wurzel

-> Die Schlüssel im rechten Teilbaum sind immer grösser als die Wurzel

Korrektheit kann mit einem rekursiven durchlaufen getestet werden (Traversierung)

Inorder-Traversierung: Der Suchbaum T wird von unten Links bis unten rechts der Reihe nach ausgegeben. Stimmt die dabei entstehende Reihenfolge ist der Suchbaum korrekt aufgebaut. (Siehe Bild)

Preorder-Traversierung: Ausgeben von Wurzel, preorder(T.links), preorder(T.rechts)

Postorder-Traversierung: Ausgeben von postorder(T.links), postorder(T.rechts), Wurzel

Worst-Case ist \(\mathcal{\Theta(n)}\) (Schlechter Pivot)

Im Durchschnitt ca. \(\Theta(log(n))\) Wuhu :)

Best Case: \(\Theta(log(n))\)

Worst Case: \(\Theta (n)\)

Mittel: \(\Theta(\sqrt{n})\)

Für jeden Knoten muss gelten, dass sich die Höhe des linken und des rechten Teilbaumes um höchstens 1 unterscheiden

\(mb(h) = F_{h+2} \approx 0,7*1.6^{h+2}\), wobei F die Fibonacci Zahlen darstellen (0, 1, 1, 2, 3, 5, 8, ...)

Herleitung: Jeder Baum hat immer genau ein Blatt mehr als innere Knoten. Ist mb die Midestblattzahl eines AVL-Baumes, dann ist mb(h) = mb(h-1) +mb(h-2).

Höhe: Nein! Denn formt man die oben genannte Formel um erhält man, dass \(h \leq 1,44*log(n)\), d.h eine Höhe, die "nur" um 44% grösser ist als die eines normalen Suchbaumes. (Das "nur" steht so in den Notizen... Finde 44% ja nicht sooo unerheblich... Aber eben. Konstante Faktoren sind in D&A egal... grml)

Wir merken uns zu jedem Knoten die aktuelle "Balance". Werde der Knoten k unter p eingefügt. Die Balance sagt aus, ob die beiden unteren Teilbäume (von p) jeweils gleich gross sind (0), der linke (-1) oder der rechte (1) grösser ist.

Falls: \(bal(p) = \pm1 \mapsto bal(p) =0\): Es muss nichts weiter unternommen werden. Die Höhe des Baums hat sich nicht geändert. 

Falls \(bal(p) = 0 \mapsto bal(p) =\pm1\): Die Höhe des Baums hat sich geändert. Entsprechend muss die Balance auch in allen Elternknoten von p angepasst werden.