Algorithmen und Datenstrukturen - Exam

Aufgabe 1)

Quick SortEffizienter Vergleichssortieralgorithmus, der das Teile-und-Herrsche-Prinzip verwendet.

• Best- und durchschnittliche Komplexität: \(O(n \log n)\)
• Schlechteste Komplexität: \(O(n^2)\) (häufig durch schlechte Pivotauswahl)
• In-place, allerdings nicht stabil
• Wichtigste Schritte: Array um ein Pivot-Element aufteilen und rekursiv sortieren
• Pivotauswahl: z.B. erstes, letztes, mittleres Element oder zufällig
• Vorteile: schneller als andere Algorithmen mit gleichem Worst-Case (für große n mit gut gewähltem Pivot)
• Nachteile: anfällig für schlechten Pivot

a)

Teilaufgabe 1:Gegeben sei das folgende Array: [9, 7, 8, 3, 2, 1, 5]. Führe den Quick Sort Algorithmus darauf durch, indem Du das erste Element als Pivot wählst. Zeige jeden Schritt des Algorithmus und notiere dabei die Zwischenzustände des Arrays. Erkläre zusätzlich, wie sich die Rekursion des Algorithmus entfaltet.

Lösung:

Teilaufgabe 1:Gegeben sei das folgende Array: [9, 7, 8, 3, 2, 1, 5]. Führe den Quick Sort Algorithmus darauf durch, indem Du das erste Element als Pivot wählst. Zeige jeden Schritt des Algorithmus und notiere dabei die Zwischenzustände des Arrays. Erkläre zusätzlich, wie sich die Rekursion des Algorithmus entfaltet.Lösung:Wir beginnen mit dem Array [9, 7, 8, 3, 2, 1, 5] und wählen das erste Element als Pivot, also 9.

• Erster Schritt: Partitionierung um das Pivot-Element 9:Array: [9, 7, 8, 3, 2, 1, 5]Links des Pivots (kleiner als 9): [7, 8, 3, 2, 1, 5]Rechts des Pivots (gleich oder größer als 9): []Neuer Zustand des Arrays: [5, 7, 8, 3, 2, 1, 9]
• Zweiter Schritt: Rekursives Sortieren der linken Seite:Array: [5, 7, 8, 3, 2, 1]Pivot: 5
  • Links des Pivots: [3, 2, 1]Rechts des Pivots: [7, 8]
  • Neuer Zustand: [1, 2, 3, 5, 7, 8, 9]
• Dritter Schritt: Rekursives Sortieren der linken Seite von [1, 2, 3, 5, 7, 8, 9] um Pivot 1:Array: [1, 2, 3]Pivot: 1
  • Neuer Zustand: [1, 2, 3, 5, 7, 8, 9]
• Vierter Schritt: Rekursives Sortieren der rechten Seite von [1, 2, 3, 5, 7, 8, 9] um Pivot 2:Array: [2, 3]Pivot: 2
  • Neuer Zustand: [1, 2, 3, 5, 7, 8, 9]
• Fünfter Schritt: Letzte Rekursion um Pivot 3:Array: [3]Pivot: 3
  • Neuer Zustand: [1, 2, 3, 5, 7, 8, 9]

Nach diesen Rekursionen ist das Array vollständig sortiert:[1, 2, 3, 5, 7, 8, 9].

b)

Teilaufgabe 2:Untenstehendes Array sei gegeben: [4, 2, 6, 9, 3]. Betrachte, dass in einem Quick Sort Algorithmus das schlechteste Szenario auftritt.

• a) Erkläre, welches Pivot-Wahlverfahren angewendet werden muss, um das schlechteste Szenario zu gewährleisten.
• b) Berechne die Anzahl der Vergleiche, die im schlimmsten Fall erforderlich sind, um dieses Array mit Quick Sort zu sortieren. Begründe ausführlich.

Lösung:

Teilaufgabe 2:Untenstehendes Array sei gegeben: [4, 2, 6, 9, 3]. Betrachte, dass in einem Quick Sort Algorithmus das schlechteste Szenario auftritt.

• a) Erkläre, welches Pivot-Wahlverfahren angewendet werden muss, um das schlechteste Szenario zu gewährleisten.
Im schlechtesten Szenario von Quick Sort wird jedes Mal das schlechteste mögliche Pivot-Element gewählt. Dies tritt ein, wenn das Pivot-Element immer das größte oder das kleinste Element des Arrays ist. Dadurch wird das Array in extrem unausgeglichene Subarrays aufgeteilt, was zu einer maximalen Tiefe der Rekursion führt.Ein solches Szenario kann erreicht werden, indem man das erste oder das letzte Element des Arrays als Pivot wählt. In unserem Beispiel-Array [4, 2, 6, 9, 3] könnten wir entweder immer das größte (letzte) oder das kleinste (erste) Element als Pivot-Element wählen, um das schlechteste Szenario zu erzielen.
• b) Berechne die Anzahl der Vergleiche, die im schlimmsten Fall erforderlich sind, um dieses Array mit Quick Sort zu sortieren. Begründe ausführlich.
Im schlimmsten Fall ist die Anzahl der Vergleiche, die benötigt werden, um ein Array der Länge n mit Quick Sort zu sortieren, wie folgt:Wenn das Array in jedem Schritt in ein Subarray der Länge n-1 und ein leeres Subarray aufgeteilt wird, ergibt sich die maximale Anzahl an Vergleichen.Für ein Array der Länge n sind im schlimmsten Fall -1 + (n-1)-1 + (n-2)-1 + ... + 2 + 1 Vergleiche nötig.Hier ein detaillierter Überblick:
• Erste Partition: n-1 Vergleiche (4 Vergleiche für das Array der Länge 5)
• Zweite Partition: (n-1)-1 Vergleiche (3 Vergleiche für das Array der Länge 4)
• Dritte Partition: (n-2)-1 Vergleiche (2 Vergleiche für das Array der Länge 3)
• Vierte Partition: 1 Vergleich (für das Array der Länge 2)
Die Summe dieser Vergleiche ist:(n-1) + (n-2) + ... + 2 + 1 = \frac{n(n-1)}{2}Setzen wir n=5 ein, erhalten wir:\frac{5×4}{2}=10Daher sind im schlimmsten Fall 10 Vergleiche notwendig, um das Array [4, 2, 6, 9, 3] zu sortieren.Fazit:
• a) Das schlechteste Szenario tritt ein, wenn das erste oder das letzte Element als Pivot gewählt wird.
• b) Die Anzahl der Vergleiche im schlimmsten Fall beträgt 10.

Aufgabe 2)

Gegeben sei eine sortierte Liste von Zählern mit den Werten \texttt{A = [1, 3, 4, 7, 8, 12, 14, 18, 20, 24]} und der Suchalgorithmus der binären Suche.

a)

Implementiere die Funktion \texttt{binaereSuche} in Python, die eine Liste \texttt{A}, einen Schlüssel \texttt{key} und die Indizes \texttt{low} und \texttt{high} als Parameter nimmt. Die Funktion soll den Index des Schlüssels in der Liste zurückgeben, wenn dieser gefunden wird. Ansonsten soll \texttt{-1} zurückgegeben werden. Verwende den gegebenen Pseudocode:

'write your code actual here' def binaereSuche(A, key, low, high):    while low <= high:        mid = (low + high) // 2        if A[mid] == key:            return mid        elif A[mid] < key:            low = mid + 1        else:            high = mid - 1    return -1

Lösung:

Hier ist die Implementierung der Funktion binaereSuche in Python, basierend auf dem gegebenen Pseudocode:

• 'write your code actual here'  def binaereSuche(A, key, low, high):     while low <= high:         mid = (low + high) // 2        if A[mid] == key:            return mid        elif A[mid] < key:            low = mid + 1        else:            high = mid - 1    return -1

Du kannst diese Funktion verwenden, um den Index eines Schlüssels in der sortierten Liste A = [1, 3, 4, 7, 8, 12, 14, 18, 20, 24] zu finden. Falls der Schlüssel nicht in der Liste ist, wird -1 zurückgegeben.

b)

Bestimme die Anzahl der Vergleiche, die im schlimmsten Fall erforderlich sind, um ein Element in einer sortierten Liste von 1024 Elementen mit binärer Suche zu finden. Begründe Deine Antwort mathematisch.

Lösung:

Die binäre Suche ist ein effizienter Algorithmus, um ein Element in einer sortierten Liste zu finden. Der schlimmste Fall tritt auf, wenn das gesuchte Element nicht in der Liste vorhanden ist oder sich am Ende der Suchoperation befindet. In jedem Schritt der binären Suche wird die zu durchsuchende Liste halbiert, sodass die maximale Anzahl der Vergleiche der logarhythmischen Basis-2-Wert der Länge der Liste ist.

Mathematisch lässt sich dies wie folgt begründen:

• Die Länge der Liste sei n. In unserem Fall ist n = 1024.
• Bei jeder Iteration wird die Liste halbiert, bis nur noch ein Element übrig bleibt. Daher müssen wir die Anzahl der Halbierungen bestimmen, die notwendig sind, um ein Element zu isolieren.
• Die Anzahl der Vergleiche im schlimmsten Fall entspricht der Anzahl der Halbierungen plus ein weiterer Vergleich am Ende.
• Die Anzahl der Halbierungen ist durch \(\text{log}_2(n)\) gegeben.
• Setzen wir n = 1024, dann erhalten wir:

\[ \text{log}_2(1024) = 10 \]

Das bedeutet, dass wir im schlimmsten Fall 10 Iterationen benötigen, um die Liste auf ein Element zu reduzieren. Außerdem ist ein zusätzlicher Vergleich notwendig, um zu überprüfen, ob das Element existiert oder nicht. Dies ergibt insgesamt 10 + 1 = 11 Vergleiche.

Also, die Anzahl der Vergleiche, die im schlimmsten Fall erforderlich sind, um ein Element in einer sortierten Liste von 1024 Elementen mit binärer Suche zu finden, beträgt 11.

c)

Nutze die binäre Suche, um das Element 18 in der gegebenen Liste \texttt{A} zu finden. Zeige alle Zwischenrechnungen und Schritte, die das Algorithmus durchführt, um das Element zu finden.

Lösung:

Die binäre Suche arbeitet durch rekursives Halbieren der Liste und Überprüfen des mittleren Elements, bis das gesuchte Element gefunden oder die Liste erschöpft ist. Hier sind die Schritte, die durchgeführt werden, um das Element 18 in der Liste A = [1, 3, 4, 7, 8, 12, 14, 18, 20, 24] zu finden:

• Initialisiere low auf 0 und high auf 9 (der letzte Index der Liste).
• Berechne den mittleren Index: mid = (low + high) // 2

Schritte:

• Erster Schritt: low = 0, high = 9 mid = (0 + 9) // 2 = 4 Vergleiche A[mid] (d.h. A[4] = 8) mit dem Schlüssel 18. Da 8 < 18, setze low = mid + 1 = 5
• Zweiter Schritt: low = 5, high = 9 mid = (5 + 9) // 2 = 7 Vergleiche A[mid] (d.h. A[7] = 18) mit dem Schlüssel 18. Da 18 == 18, ist der Schlüssel gefunden. Gib den Index 7 zurück.

Damit wurde das Element 18 in der Liste A nach 2 Iterationen gefunden. Der Index des Schlüssels 18 ist 7.

Aufgabe 3)

Gegeben sei ein ungerichteter Graph G mit einer Menge von Knoten V und einer Menge von Kanten E. In diesem Graphen sind die Kanten durch nicht-geordnete Paare von Knoten dargestellt. Der Graph wird durch eine Adjazenzmatrix beschrieben, wobei M[i][j] = 1 angibt, dass eine Kante zwischen den Knoten i und j existiert, ansonsten ist M[i][j] = 0.

a)

• Teilaufgabe a: Schreibe einen Algorithmus in Python, der überprüft, ob der Graph G zusammenhängend ist. Ein Graph ist zusammenhängend, wenn es einen Pfad zwischen jedem Paar von Knoten gibt. Implementiere Deinen Algorithmus und erkläre die Funktionsweise.

def ist_zusammenhaengend(matrix):    num_knoten = len(matrix)    besucht = [False] * num_knoten    def dfs(knoten):        besucht[knoten] = True        for nachbar, kante in enumerate(matrix[knoten]):            if kante == 1 and not besucht[nachbar]:                dfs(nachbar)    dfs(0)    return all(besucht)# Beispiel für eine Adjazenzmatrixgraph_matrix = [    [0, 1, 0, 0],    [1, 0, 1, 1],    [0, 1, 0, 0],    [0, 1, 0, 0]]print(ist_zusammenhaengend(graph_matrix))

Lösung:

Teilaufgabe a: Hier ist der Python-Algorithmus, um zu überprüfen, ob der gegebene Graph G zusammenhängend ist. Ein Graph ist zusammenhängend, wenn es einen Pfad zwischen jedem Paar von Knoten gibt. Der Algorithmus verwendet eine Tiefensuche (Depth-First Search, DFS), um festzustellen, ob alle Knoten besucht wurden.

Funktionsweise des Algorithmus:

• Erstelle eine Liste besucht, die für jeden Knoten speichert, ob er besucht wurde (initial auf False gesetzt).
• Definiere die rekursive Funktion dfs, die einen bestimmten Knoten besucht und alle seine Nachbarn rekursiv besucht.
• Starte die Tiefensuche bei Knoten 0 (oder einem beliebigen anderen Knoten).
• Prüfe, ob alle Knoten besucht wurden. Wenn ja, ist der Graph zusammenhängend; andernfalls nicht.

def ist_zusammenhaengend(matrix):    num_knoten = len(matrix)    besucht = [False] * num_knoten    def dfs(knoten):        besucht[knoten] = True        for nachbar, kante in enumerate(matrix[knoten]):            if kante == 1 and not besucht[nachbar]:                dfs(nachbar)    dfs(0)    return all(besucht)# Beispiel für eine Adjazenzmatrixgraph_matrix = [    [0, 1, 0, 0],    [1, 0, 1, 1],    [0, 1, 0, 0],    [0, 1, 0, 0]]print(ist_zusammenhaengend(graph_matrix))

Erklärung des Beispielcodes:

• Die Adjazenzmatrix graph_matrix stellt einen Graphen mit 4 Knoten dar.
• Die Funktion ist_zusammenhaengend wird aufgerufen, um zu überprüfen, ob der Graph zusammenhängend ist.
• Im Beispiel gibt die Funktion print(ist_zusammenhaengend(graph_matrix)) True aus, da alle Knoten in dem gegebenen Graphen verbunden sind.

b)

• Teilaufgabe b: Bestimme die Komplexität Deines Algorithmus aus Teilaufgabe a in Big-O-Notation. Erkläre Deine Herleitung detailliert und berücksichtige dabei die Anzahl der Knoten |V| und die Anzahl der Kanten |E|.

Lösung:

Teilaufgabe b: Jetzt bestimmen wir die Komplexität des Algorithmus aus Teilaufgabe a in Big-O-Notation und erklären die Herleitung im Detail.

• Initialisierung: Die Liste besucht wird mit einer Größe von \(|V|\) initialisiert, was einen Aufwand von \(\text{O}(|V|)\) darstellt.
• Tiefensuche (DFS): Die Tiefensuche wird in der Funktion dfs durchgeführt. Jeder Knoten wird genau einmal als besucht markiert, also haben wir einen Aufwand von \(\text{O}(|V|)\) für die Knoten.
• Für jeden Knoten iterieren wir über dessen Nachbarn, um die existierenden Kanten zu überprüfen. Diese Kantenprüfung dauert für jeden Knoten \(|V|\) (da die Adjazenzmatrix der Größe \(|V| \times |V|\) ist). Das bedeutet für die gesamte Iteration über alle Knoten \(|V|\) eine Komplexität von \(\text{O}(|V|^2)\).

• Gesamte Komplexität des Algorithmus: Da die Tiefensuche in \(\text{O}(|V| + |E|)\) durchgeführt wird und wir \(\text{O}(|V|)\) und \(\text{O}(|V|^2)\) Aufwände haben, ergibt sich die insgesamt dominierende Komplexität (das höchste Wachstum) des Algorithmus als \(\text{O}(|V|^2)\). Das bedeutet:
• Die Gesamte Laufzeitkomplexität des Algorithmus ist \(\text{O}(|V|^2)\).

Zusammenfassung:Der Hauptfaktor bei der Bestimmung der Komplexität war die Tatsache, dass wir eine Adjazenzmatrix verwenden, wodurch der Aufwand für die Überprüfung der Kanten \(|V|\) beträgt, was für insgesamt \(|V|\) Knoten zu einem Aufwand von \(\text{O}(|V|^2)\) führt. Selbst wenn der Graph spärlich ist (d.h. \(|E| \text{ist viel kleiner als } |V|^2\)), bleibt die Komplexität aufgrund der Verwendung einer Adjazenzmatrix \(\text{O}(|V|^2)\).

c)

• Teilaufgabe c: Zeige anhand eines Beispiels, wie der Dijkstra-Algorithmus zur Bestimmung des kürzesten Pfades in einem gewichteten, gerichteten Graphen funktioniert. Du kannst dazu eine einfache 4-Knoten-Graph-Darstellung verwenden und die Schritte des Algorithmus aufzeigen.

Lösung:

Teilaufgabe c: Um den Dijkstra-Algorithmus zur Bestimmung des kürzesten Pfades in einem gewichteten, gerichteten Graphen zu demonstrieren, werden wir ein einfaches Beispiel mit einem 4-Knoten-Graphen verwenden.

Beispiel-Graph:

• Knoten: A, B, C, D
• Kanten und Gewichte: - A → B: 1 - A → C: 4 - B → C: 2 - B → D: 5 - C → D: 1

Adjazenzmatrix:

graph = {    'A': {'B': 1, 'C': 4},    'B': {'C': 2, 'D': 5},    'C': {'D': 1},    'D': {}}

Schritte des Dijkstra-Algorithmus:

• 1. Initialisierung: - Wähle den Startknoten (z.B. A). - Setze die Distanz zu jedem anderen Knoten auf Unendlich und die Distanz zum Startknoten auf 0. - Erstellt eine leere Menge, um besuchte Knoten zu speichern, und eine Menge, um Knoten zu speichern, deren kürzeste Distanz gefunden wurde.
• Unbesuchte Knoten: {A, B, C, D}Besuchte Knoten: {}Distanzen: {A: 0, B: ∞, C: ∞, D: ∞}
• 2. Auswahl des Knoten mit der geringsten aktuellen Distanz: - A hat die geringste Distanz (0).
• Aktueller Knoten: A
• 3. Aktualisiere die Distanzen der Nachbarn von A: - Distanz zu B: min(∞, 0 + 1) = 1 - Distanz zu C: min(∞, 0 + 4) = 4
• Distanzen: {A: 0, B: 1, C: 4, D: ∞}
• 4. Verschiebe A zu den besuchten Knoten:Unbesuchte Knoten: {B, C, D}Besuchte Knoten: {A}
• 5. Auswahl des Knoten mit der geringsten aktuellen Distanz: - B hat die geringste Distanz (1).
• Aktueller Knoten: B
• 6. Aktualisiere die Distanzen der Nachbarn von B: - Distanz zu C: min(4, 1 + 2) = 3 - Distanz zu D: min(∞, 1 + 5) = 6
• Distanzen: {A: 0, B: 1, C: 3, D: 6}
• 7. Verschiebe B zu den besuchten Knoten:Unbesuchte Knoten: {C, D}Besuchte Knoten: {A, B}
• 8. Auswahl des Knoten mit der geringsten aktuellen Distanz: - C hat die geringste Distanz (3).
• Aktueller Knoten: C
• 9. Aktualisiere die Distanzen der Nachbarn von C: - Distanz zu D: min(6, 3 + 1) = 4
• Distanzen: {A: 0, B: 1, C: 3, D: 4}
• 10. Verschiebe C zu den besuchten Knoten:Unbesuchte Knoten: {D}Besuchte Knoten: {A, B, C}
• 11. Auswahl des Knoten mit der geringsten aktuellen Distanz: - D hat die geringste Distanz (4).
• Aktueller Knoten: D
• 12. Aktualisiere die Distanzen der Nachbarn von D: - D hat keine Nachbarn.
• Endzustand:Distanzen: {A: 0, B: 1, C: 3, D: 4}Besuchte Knoten: {A, B, C, D}
• Die kürzesten Distanzen vom Startknoten A zu den anderen Knoten sind: - Distanz zu B: 1 - Distanz zu C: 3 - Distanz zu D: 4

Python-Implementation:

import heapqdef dijkstra(graph, start):    dijkstra_distanzen = {knoten: float('inf') for knoten in graph}    dijkstra_distanzen[start] = 0    pq = [(0, start)]    while pq:        aktuelle_distanz, aktueller_knoten = heapq.heappop(pq)        if aktuelle_distanz > dijkstra_distanzen[aktueller_knoten]:            continue        for nachbar, gewicht in graph[aktueller_knoten].items():            distanz = aktuelle_distanz + gewicht            if distanz < dijkstra_distanzen[nachbar]:                dijkstra_distanzen[nachbar] = distanz                heapq.heappush(pq, (distanz, nachbar))    return dijkstra_distanzen# Beispiel-Graphgraph = {    'A': {'B': 1, 'C': 4},    'B': {'C': 2, 'D': 5},    'C': {'D': 1},    'D': {}}start_knoten = 'A'schirtt = dijkstra(graph, start_knoten)print(schirtt)

Erklärung des Beispielcodes:

• Das Graph-Dictionary repräsentiert den gewichteten gerichteten Graphen.
• Die Funktion dijkstra berechnet die kürzesten Pfade von einem Startknoten zu allen anderen Knoten im Graphen.
• Die Ergebnisse zeigen die kürzesten Distanzen vom Startknoten A zu anderen Knoten.

d)

• Teilaufgabe d: Berechne das kürzeste Pfad-Problem im Kontext eines ungewichteten Graphen, indem Du die Anzahl der Kanten auf dem kürzesten Weg bestimmst. Nutze dazu die Breitensuche (BFS) und beschreibe den Algorithmus und seine Komplexität.

Lösung:

Teilaufgabe d: Zur Berechnung des kürzesten Pfades in einem ungewichteten Graphen verwenden wir die Breitensuche (Breadth-First Search, BFS). In einem ungewichteten Graphen entspricht der kürzeste Pfad zwischen zwei Knoten der minimalen Anzahl an Kanten, die diese Knoten verbinden.Hier ist eine detaillierte Beschreibung des Algorithmus und seine Komplexität:

Algorithmus:

• 1. Initialisierung: - Erstelle eine Queue, um die Knoten für die BFS zu speichern. - Erstelle eine Liste distanzen, die die Anzahl der Kanten (Distanz) zu jedem Knoten speichert und initial auf Unendlich setzt, außer für den Startknoten, der auf 0 gesetzt wird. - Füge den Startknoten zur Queue hinzu.
• 2. BFS-Durchführung: - Solange die Queue nicht leer ist, wiederhole folgende Schritte: -- Nimm den aktuellen Knoten aus der Queue. -- Für jeden Nachbarn des aktuellen Knotens: --- Wenn der Nachbar noch nicht besucht wurde (Distanz ist unendlich): ---- Setze die Distanz des Nachbarn auf die Distanz des aktuellen Knotens plus 1. ---- Füge den Nachbarn zur Queue hinzu.
• 3. Rückgabe: - Die Liste distanzen enthält die kürzesten Distanzen von dem Startknoten zu allen anderen Knoten im Graphen.

Komplexität: - Die Zeitkomplexität des BFS-Algorithmus beträgt \(\text{O}(|V| + |E|)\), da jeder Knoten und jede Kante im schlimmsten Fall genau einmal besucht werden. - Die Raumkomplexität beträgt ebenfalls \(\text{O}(|V|)\) aufgrund der Speicherung der Queue und der distanzen-Liste.Python-Implementation:

from collections import dequedef bfs_kurzeste_pfade(matrix, start):    num_knoten = len(matrix)    distanzen = [float('inf')] * num_knoten    distanzen[start] = 0    queue = deque([start])    while queue:        aktueller_knoten = queue.popleft()        for nachbar, kante in enumerate(matrix[aktueller_knoten]):            if kante == 1 and distanzen[nachbar] == float('inf'):                distanzen[nachbar] = distanzen[aktueller_knoten] + 1                queue.append(nachbar)    return distanzen# Beispiel für eine Adjazenzmatrixgraph_matrix = [    [0, 1, 0, 0],    [1, 0, 1, 1],    [0, 1, 0, 1],    [0, 1, 1, 0]]start_knoten = 0distanzen = bfs_kurzeste_pfade(graph_matrix, start_knoten)print(distanzen)

Erklärung des Beispielcodes:

• Die Adjazenzmatrix graph_matrix repräsentiert den ungewichteten Graphen.
• Die Funktion bfs_kurzeste_pfade berechnet die Anzahl der Kanten auf den kürzesten Wegen vom start_knoten zu allen anderen Knoten.
• Die Ausgabe zeigt die kürzesten Distanzen (in Anzahl der Kanten) von Knoten 0 (Startknoten) zu allen anderen Knoten.

Beispielausgabe:[0, 1, 2, 2]Erklärung: Vom Startknoten 0 benötigst Du: - 0 Kanten, um zu sich selbst zu gelangen - 1 Kante, um zu Knoten 1 zu gelangen - 2 Kanten, um zu Knoten 2 zu gelangen - 2 Kanten, um zu Knoten 3 zu gelangen.

Aufgabe 4)

Gegeben sei ein AVL-Baum, ein selbstbalancierender binärer Suchbaum, der sicherstellt, dass die Höhenbalance für jeden Teilbaum gewahrt bleibt. Ein AVL-Baum hat die folgenden Eigenschaften:

• Der Balance-Faktor eines Knotens ist definiert als der maximale Unterschied der Höhen von linken und rechten Teilbaum und muss ≤ 1 sein.
• Einfüge- und Löschoperationen werden durch Rotationen ausgeglichen, um die Balance aufrechtzuerhalten.
• Die Komplexität dieser Operationen beträgt O(log n) für Einfügen, Löschen und Suchen.
• Es gibt vier Typen von Rotationen, um den Baum auszugleichen:
  • LL-Rotation (Links-Links)
  • RR-Rotation (Rechts-Rechts)
  • LR-Rotation (Links-Rechts)
  • RL-Rotation (Rechts-Links)

a)

Gegeben ist ein leerer AVL-Baum. Füge folgende Knoten in der Reihenfolge {10, 20, 30, 40, 50, 25} ein und zeige die Baumstruktur nach jeder Einfügeoperation sowie alle nötigen Rotationen, die angewendet wurden, um den Baum balanciert zu halten.

Lösung:

Um den AVL-Baum gemäß der angegebenen Reihenfolge von Knoten {10, 20, 30, 40, 50, 25} zu erstellen und die Baumstruktur nach jeder Einfügeoperation sowie alle notwendigen Rotationen zu zeigen, gehen wir Schritt für Schritt vor:

• Einfügen von 10:

Der Baum ist leer, daher wird 10 die Wurzel des AVL-Baums.

 '10' 

• Einfügen von 20:

Füge 20 ein. Da 20 größer ist als 10, wird 20 der rechte Knoten von 10.

 '   10           20' 

• Einfügen von 30:

Füge 30 ein. Da 30 größer ist als 20, wird 30 der rechte Knoten von 20. Dies erzeugt eine Rechts-Rechts-Schieflage, die durch eine einzelene Linksrotation (LL-Rotation) korrigiert wird.

    'Einfügen   10           20                 30' 

Nach der LL-Rotation:

 '   20  /   10   30' 

• Einfügen von 40:

Füge 40 ein. Da 40 größer ist als 30, wird 40 der rechte Knoten von 30.

 '    20  /   10   30                   40' 

• Einfügen von 50:

Füge 50 ein. Da 50 größer ist als 40, wird 50 der rechte Knoten von 40. Dies erzeugt erneut eine Rechts-Rechts-Schieflage, die durch eine einzelene Linksrotation (LL-Rotation) bei 30 korrigiert wird.

 '    20  /   10   30                 40                       50' 

Nach der LL-Rotation:

 '    20  /   10   40      /       30   50' 

• Einfügen von 25:

Füge 25 ein. Da 25 zwischen 20 und 30 liegt, wird 25 der linke Knoten von 30. Dies erzeugt eine Links-Rechts-Schieflage, die durch eine LR-Rotation korrigiert wird.

 '    20  /   10   40      /       30   50    /    25' 

Nach der LR-Rotation bei 40:

 '    20  /   10   30      /       25   40                        50' 

Dies ist der endgültige AVL-Baum nach dem Einfügen aller angegebenen Knoten mit den notwendigen Rotationen.

b)

Zwei weitere Knoten, 5 und 35, sollen nun zu dem entstandenen AVL-Baum hinzugefügt werden. Beschreibe detailiert den Einfügeprozess und die nötigen Rotationen (falls vorhanden), um die AVL-Balance zu bewahren. Zeichne die Baumstrukturen nach jedem Schritt.

Lösung:

Um die AVL-Baum-Balance nach dem Einfügen der Knoten 5 und 35 zu beschreiben, gehen wir Schritt für Schritt vor:

Aktueller Zustand des AVL-Baums:

 '    20  /   10   30      /       25   40                        50' 

• Einfügen von 5:

Füge 5 ein. Da 5 kleiner ist als 10, wird 5 der linke Knoten von 10.

 '    20  /    10   30      /  5    25   40                        50' 

• Überprüfen des Balance-Faktors:
• Der Balance-Faktor des Knotens 10 ist 1 (|Höhe links - Höhe rechts| = |1 - 0|).
• Der Balance-Faktor des Knotens 20 ist weiterhin innerhalb der erlaubten Grenzen (|Höhe links - Höhe rechts| = |2 - 2| = 0).

Daher sind keine Rotationen nötig.

• Einfügen von 35:

Füge 35 ein. Da 35 größer ist als 30 und kleiner als 40, wird 35 der linke Knoten von 40.

 '    20  /    10   30      /  5    25   40                   35    50' 

• Überprüfen des Balance-Faktors:
• Der Balance-Faktor des Knotens 40 ist 1 (|Höhe links - Höhe rechts| = |1 - 1| = 0).
• Der Balance-Faktor des Knotens 30 ist 1 (|Höhe links - Höhe rechts| = |1 - 2| = 1).
• Der Balance-Faktor des Knotens 20 bleibt ebenfalls innerhalb der erlaubten Grenzen (|Höhe links - Höhe rechts| = 2 - 3 = 1).

Daher sind keine Rotationen nötig.

Endgültiger Zustand des AVL-Baums nach dem Einfügen von 5 und 35:

 '    20  /    10   30      /   5   25   40                   35    50' 

Der Baum ist weiterhin balanciert, und keine zusätzlichen Rotationen sind erforderlich.

c)

Erkläre das Verfahren, um einen Knoten mit dem Wert 20 aus dem entstandenen AVL-Baum zu löschen. Welche speziellen AVL-Eigenschaften und Rotationen müssen beachtet werden und wie verändert sich die Baumstruktur nach dem Löschen von 20? Dokumentiere alle Schritte.

Lösung:

Um den Knoten mit dem Wert 20 aus dem AVL-Baum zu löschen und sicherzustellen, dass der Baum balanciert bleibt, gehen wir Schritt für Schritt vor:

Aktueller Zustand des AVL-Baums:

 '    20  /    10   30  /   5   25   40  /   35   50' 

• Schritt 1: Löschen des Knotens 20:

Wähle eine von zwei möglichen Vorgehensweisen, wenn der zu löschende Knoten zwei Kinder hat. Ersetze den Knoten durch dessen in-order Nachfolger, was der kleinste Wert im rechten Teilbaum ist – in diesem Fall ist das der Knoten 25:

 ' Der 20 wird mit seinem in-order Nachfolger (25) ersetzt' 

Neuer Zustand des Baums nach Ersetzen:

 '    25  /    10   30  /   5   25   40  /   35   50' 

• Schritt 2: Löschen des Knotens 25:

Als nächstes wird der Knoten 25 aus dem rechten Teilbaum gelöscht. Da er kein Kind hat, kann er einfach entfernt werden:

 '   25  /    10   30  /   5     40  /   35   50' 

• Überprüfen des Balance-Faktors:
• Der Balance-Faktor des Knotens 30 ist 0 (|Höhe links - Höhe rechts| = |0 - 1|).
• Der Balance-Faktor des Knotens 25 ist 1 (|Höhe links - Höhe rechts| = |1 - 2| = 1).
• Der Baum ist ausgeglichen, daher sind keine weiteren Rotationen erforderlich.

Endgültiger Zustand des AVL-Baums nach dem Löschen von 20:

 '   25  /   10   30  /    5    40  /  35   50' 

Zusammengefasst:

• Ersetze 20 durch dessen in-order Nachfolger 25.
• Lösche 25 aus dem rechten Teilbaum.
• Überprüfe und bestätige die Balance-Faktoren, um sicherzustellen, dass die AVL-Bedingung erfüllt bleibt.