Datenstrukturen und Algorithmen

Beginnend bei der Baumwurzel werden die Ebenen von links nach rechts durchlaufen.

Für jeden (inneren) Knotne ist der Betrag der Differenz der Höhen des linken und rechten Teilbaumes maximal 1.

1. Einfügen in linken Teilbaum des linken Kindes
→ Rotation mit linkem Kind
2. Einfügen in rechten Teilbaum des linken Kindes
→ Doppelrotation mit linkem Kind
3. Einfügen in rechten Teilbaum des rechten Kindes
→ Rotation mit rechtem Kind
4. Einfügen in linken Teilbaum des rechten Kindes
→ Doppelrotation mit rechtem Kind

1 und 3 sowie 2 und 4 sind symmetrische Problemfälle

Ein Baum, in dem jeder Knoten zwei, drei oder maximal vier Kinder besitzt und entsprechend ein, zwei oder maximal drei Datenelemente speichert, die nach dem gewählten Ordnungskriterium aufsteigend sortiert sind.

Ein Rot-Schwarz-Baum ist ein binärer Suchbaum, in dem jedem Knoten ein 
Farbattribut zugeordnet ist, so dass gilt:
1. Jeder Knoten ist entweder rot oder schwarz
2. Jeder Blattknoten (Null-Knoten) ist per Definition schwarz
3. Die Kinder jedes roten Knotens sind schwarz
4. Für jeden Knoten k gilt: Jeder Pfad von k zu einem Blatt enthält die gleiche 
Anzahl schwarze Knoten („Schwarztiefe“)

.Jeder Knoten außer der Wurzel enthält  zwischen m und 2m Schlüsselwerte.

m heißt Ordnung des B-Baums

Im inneren Knoten i Schlüsselwerte (m ≤ i ≤ 2m), i+1 Unterbäume

Anmerkung: Bei B-Bäumen spricht man auch von „Seiten“ statt von 
„Knoten“ (Seiten = Speichereinheiten auf einem externen Medium)

Ein Trie oder Präfixbaum ist eine Datenstruktur, die zum Suchen nach Zeichenfolgen erwendet wird. Es handelt sich dabei um einen speziellen Suchbaum zur gleichzeitigen Speicherung mehrerer Zeichenketten. Dabei beinhalten Tries eine Art der Datenkompression da gemeinsame Präfixe der Zeichenketten nur einmal gespeichert werden.

• lange gemeinsame Teilworte, z.B. URLs oder Pfadnamen
• nicht vorhandene Buchstaben und Buchstabenkombinatinen
• möglicherweise fast leere Knoten
• sehr unausgeglichene Bäume

Lösung: Überspringen von Teilworten mit Patricia Baum

In Knoten werden Teilworte (und Länge) des zu überspringenden Wortteils gespeichert und für Verzweigung zu testendes Zeichen. 

Die Eingabe ist ein Array mit zu sortierenden Elementen. Als erstes wird die Eingabe in einen binären Max-Heap überführt. Aus der Heap-Eigenschaft folgt direkt, dass nun an der ersten Array-Position das größte Element steht. Dieses wird mit dem letzten Array-Element vertauscht und die Heap-Array-Größe um 1 verringert, ohne den Speicher freizugeben. Die neue Wurzel des Heaps kann die Heap-Eigenschaft verletzen. Die Heapify-Operation korrigiert gegebenenfalls den Heap, so dass nun das nächstgrößere bzw. gleich große Element an der ersten Array-Position steht. Die Vertausch-, Verkleiner- und Heapify-Schritte werden so lange wiederholt, bis die Heap-Größe 1 ist. Danach enthält das Eingabe-Array die Elemente in aufsteigend sortierter Reihenfolge.

Aufwand besteht im Wesentlichen aus 2 Teilen:

Aufbau des Heaps

–Durchsickern von \(\frac{n}{2}\) Elemente entlang eines Pfades im Baum. Pfad ist im ungünstigsten Fall Höhe des Baums \(\log_2n\).

–Somit insgesamt: \(\frac{n}{2} \cdot \log_2n\)

Entfernen der Elemente zur eigentlichen Sortierung

–Entfernen aller \(n\) Elemente und wiederherstellen der Heap-Eigenschaft durch „durchsickern“ im Pfad

–Insgesamt: \(n \cdot \log_2n\)

Gesamtaufwand

\(\frac{3n}{2} \cdot \log_2n\), somit \(\mathcal{O}(n \cdot \log_2n)\)

Im durchschnittlichen Fall wie MergeSortund QuickSort Aber auch im schlechtesten Fall \(\mathcal{O}(n \cdot \log_2n)\)!

•  QuickSort und HeapSort haben ähnliche Laufzeitkomplexität (meist \(\mathcal{O}(n \ \log_2 n)\))
•  QuickSort ist in der Praxis meist etwas schneller als HeapSort, im schlechtesten Fall jedoch \(\mathcal{O}(n^2)\)
•  Dieser „schlechteste Fall“ tritt nur selten auf, doch kann er z.B. in laufzeitkritischen Systemen ein Argument für HeapSort sein

•  HeapSort = in-place <-> MergeSort = out-of-place (normalerweise)
• HeapSort = instabil <-> MergeSort = stabil
• MergeSort kann leichter parallelisiert werden
• MergeSort eignet sich gut für externes Sortieren (ursprüngliche Motivation)

Gegeben ist eine Kantenliste für 

Die erste Zahl (6) steht für die Knotenzahl. Die zweite Zahl (11) steht für die Kantenzahl. Die weiteren Paare (1,2 ; 1,3...) stehen für die Kanten.

6,11,1,2,1,3,3,1,4,1,3,4,3,6,5,3,5,5,6,5,6,2,6,4

Gegeben ist eine Knotenliste für G

6,11,2,2,3,0,3,1,4,6,1,1,2,3,5,3,2,4,5

Die Teilfolge 2,2,3 bedeutet, dass der Knoten 1 den Ausgangsgrad 2 hat und herausgehende Kanten zu den Knoten 2 und 3.

Knotenlisten benötigen weniger Speicherplatz als Kantenlisten

- Kantenlisten: 2 + 2 · lE l

 -  Knotenlisten: 2 + lV l + lE l

… haben dafür aber eine höhere Zeitkomplexität

Adjazenz bedeutet berühren oder aneinander grenzen.  Einträge werden für direkte Nachbarschaften verwendet. A ist eine Adjazenzmatrix für den Graph \(G=(V,E): (A_{ij})=\psi~genau~dann~wenn~(i,j) \in E\)

\(A=\begin{pmatrix} 0 & 0 & 12 & 60 & 0\\ 10 & 0 & 0 & 0 & 0\\ 0 & 20 & 0 & 32 & 0\\ 0 & 0 & 0 & 0 & 0\\ 7 & 0 & 0 & 0 & 0\\ \end{pmatrix}\)

Die Adjazenzliste (oder auch Nachbarschaftsliste) ist eine Möglichkeit, Graphen im Computer zu speichern. Sie wird in ihrer einfachsten Form durch eine einfach verkettete Liste aller Knoten des Graphen dargestellt, wobei jeder Knoten eine Liste aller seiner Nachbarn (in ungerichteten Graphen) bzw. Nachfolger (in gerichteten Graphen) besitzt.

\(\begin{matrix} \underline{Operation} & \underline{Kantenliste} & \underline{Knotenliste} & \underline{Adjazenzmatrix} & \underline{Adjazenzliste}\\ \textbf{Einfügen Kanten} & \mathcal{O}(1) & \mathcal{O}(n+m) & \mathcal{O}(1) & \mathcal{O}(1)/\mathcal{O}(n) \\ \textbf{Löschen von Kanten} & \mathcal{O}(m) & \mathcal{O}(n+m) & \mathcal{O}(1) & \mathcal{O}(n) \\ \textbf{Einfügen Knoten} & \mathcal{O}(1) & \mathcal{O}(1) & \mathcal{O}(n^2) & \mathcal{O}(1) \\ \textbf{Löschen Knoten} & \mathcal{O}(m) & \mathcal{O}(n+m) & \mathcal{O}(n^2) & \mathcal{O}(n+m) \\ \end{matrix} \)

Ein Weg (u0,u1,...,uk) heißt Eulerscher Weg, wenn jede Kante des

Graphen genau einmal in seinem Pfad vorkommt.

Er heißt Eulerscher Kreis, wenn zusätzlich uk=u0 ist.

Wenn es Knoten mit ungeradem Ausgangsgrad gibt. 

Realisierung für ungerichteteGraphen:

1.Bestimme den Knoten, an dem die Suche beginnen soll, und speichere ihn in einer Warteschlange (Queue)

2.Entnimm einen Knoten vom Beginn der Warteschlange und markiere ihn.

Falls das gesuchte Element gefunden wurde, brich die Suche ab und liefere „gefunden“ zurück.

Anderenfalls hänge alle bisher unmarkierten Nachfolger dieses Knotens, die sich noch nicht in der Warteschlange befinden, ans Ende der Warteschlange an.

3.Wenn die Warteschlange leer ist, dann wurde jeder Knoten bereits untersucht. Beende die Suche und liefere „nicht gefunden“ zurück.

4.Wiederhole Schritt 2.

1.Bestimme den Knoten, an dem die Suche beginnen soll

2.Speichere den kleinsten/größten (optional) alle noch nicht erschlossenen Nachfolger in einem Stack

3.Rufe rekursiv für jeden der Knoten im Stack die Tiefensuche auf

• Falls der Stack leer sein sollte, liefere „nicht gefunden“ zurück
• Falls es keine nicht erschlossenen Nachfolger mehr gibt, lösche den obersten Knoten aus dem Stackund rufe für den jetzt oberen Knoten im Stack die Tiefensuche auf
• Falls das gesuchte Element gefunden wurde, brich die Suche ab und liefere ein Ergebnis

Eine Sortierung, bei der Abhängigkeiten benutzt werden. Zuerst wird ein beliebiger Knoten ohne Vorgänger gewählt und entfernt (in ein Sortierfeld geschrieben). Dadurch ändern sich auch die Vorgängerzahlen ander Elemente (um -1) und es entstehen neue Elemente ohne Vorgänger, die entfernt werden können. Hat man alle Elemente entfernt, bildet das Sortierfeld die Topologische Sortierung.

Ungerichtete und zyklische Graphen sind nicht topologisch sortierbar!

Berechnet kürzesten Pfad von einem Startknoten zu allen anderen

Grundidee: folge immer derjenigen Kante, die den kürzesten

Streckenabschnitt vom Startknoten aus verspricht iterative Erweiterung einer Menge von „billig“erreichbaren Knoten

Greedy-Algorithmus

• ähnlich Breitensuche nur für nichtnegative Gewichte
• berechnet (iterativ verfeinernd) Distanzwerte D
• Prioritätswarteschlange zum Herauslesen des jeweils minimalen Elements

Kostenwerte für Knoten u:

g(u): Bisherige Kosten vom Startknoten bis u h(u): Geschätzte Kosten von u bis zum Ziel f(u): Kosten vom Start zum Ziel über u: f(u) = g(u) + h(u) Knoten werden in 3 Gruppen eingeteilt:

OPEN: Alle Knoten, zu denen ein Weg gefunden wurde (dieser ist nicht notwendigerweise optimal). Speichere f-Wert für jeden Knoten.

Im nächsten Schritt wird der Knoten mit dem kleinsten f-Wert entnommen.

CLOSED: Alle Knoten, zu denen der kürzeste Weg bekannt ist.

Alle anderen Knoten: noch gar nicht betrachtet

Negative Kantengewichte sind nicht zugelassen. Lösung: Bellman-Ford-Algorithmus.

Der Bellmann-Ford-Algorithmus berechnet den kürzesten Weg in einem kantengewichteten Graphen, ausgehend von einem Startknoten. Anders als bei Dijkstra und A* sind auch negative Kantengewichte zulässig, jedoch keine negativen Zyklen!

Setze alle Knoten bis auf den Startknoten auf unendlich. Ausgehend vom Startknoten berechne den Weg zu den Nachfolgeknoten (alle erreichbaren). Wenn der errechnete Weg kleiner als der schon in Erfahrung gemachte Weg (am Anfang unendlich), dann aktualisiere. 
Der Algorithmus erforderte mehrere Durchläufe.

Der Algorithmus von Kruskal ist ein Greedy-Algorithmus der Graphentheorie zur Berechnung minimaler Spannbäume von ungerichteten Graphen. Der Graph muss dazu zusätzlich zusammenhängend, kantengewichtet und endlich sein.

1. Erstelle eine Liste mit allen Kantengewichten sortiert nach Gewicht.
2. Markiere die Kanten mit den niedrigen Gewichten zuerst und prüfe, ob es einen Zyklus gibt. Falls ja, dann streiche diese Kante.
3. Fahre mit der nächst höheren Kante fort.

Der Algorithmus von Ford-Fulkerson berechnet den maximalen Durchfluß in einem gerichteten und gewichteten Graphen bei gegebenem Start- und Endpunkt.

1. Wähle einen Pfad vom Start zum Ziel.
2. Entnimm diesem Pfad den minimalen Durchfluß und ändere alle Kantengewichte dahingehend (Kantengewicht - minimalen Durchfluß)
3. Zeichne die Rückrichtungen mit dem Kantengewicht des Minimalen Durchflußes. Dadurch entstehen neue Kanten.
4. Fahre fort bis keine Pfad mehr möglich.

Intuitive Idee: 

• Muster von links nach rechts über Text schieben und 
 jeweils „übereinander liegende“ Zeichen vergleichen

• Muster eine Position nach rechts verschieben, 
 sobald Abweichung

• Abbruch, wenn kompletter Match

Der Knuth-Morris-Pratt-Algorithmus ist String-Matching-Algorithmus, der im Vergleichsfenster einen Verschiebung um mehr als ein Zeichen ermöglicht. Hierzu wird vorher eine Präfixtabelle berechnet. 

• ab: a gefolgt von b (Konkatenation)
• a|b: a oder b (Disjunktion)
• . : beliebiger Buchstabe (Wildcard)
• a* : beliebige Anzahl von a
• a+ : beliebige Anzahl größer 0 von a (mindestens einmal)
• a? : genau 0 oder 1 mal a
• [abc] : irgend ein Buchstabe der Aufzählung
• ^ und $ : Spezialzeichen für Zeilenbeginn und Zeilenende
• ( ) : Gruppierung