Aufgabe 2 - Suchbäume · Abitur NRW Informatik LK · Nachtermin 2022

a) Stellen Sie den Suchbaum mit sämtlichen darin verwalteten Kontakten (jeweils mit Schlüssel und Anzahl der zugehörigen Begegnungen) dar, der entsteht, nachdem alle Begegnungen aus Abbildung 3 verarbeitet wurden.

Lösung:

a) Begründen Sie, weshalb ein Suchbaum zur Verwaltung der Kontakte besser geeignet ist als eine lineare Liste.

Lösung: Grundsätzlich eignen sich sowohl ein Suchbaum als auch eine lineare Liste, um eine beliebige Anzahl von Objekten des gleichen Typs nach einem bestimmten Attribut sortiert zu verwalten. Bei der Verarbeitung einer neuen Begegnung muss zunächst nach einem Kontakt zum Schlüssel der Begegnung gesucht werden, um zu prüfen, ob dieser bereits zuvor angelegt wurde. Ist dies nicht der Fall, muss er als neuer Kontakt an der richtigen Stelle bzgl. der gewünschten Sortierung eingefügt werden. Bei einer Liste wird diese von vorne beginnend elementweise durchlaufen, bis der bereits existierende Kontakt bzw. die Einfügestelle des neu anzulegenden Kontakts gefunden wurde. Im Gegensatz dazu halbiert sich bei einem optimal besetzten Suchbaum die Anzahl der zu betrachtenden Elemente mit jedem Schritt, so dass der Kontakt bzw. die Einfügestelle im Durchschnitt erheblich schneller (d. h. mit weniger durchzuführenden Operationen) gefunden werden kann. Ein Suchbaum kann im ungünstigsten Fall vollständig zu einer linearen Liste entarten und keinen Vorteil mehr gegenüber dieser besitzen. Dies erscheint im vorliegenden Sachzusammenhang unwahrscheinlich, da die Schlüssel aus zufälligen Zeichenfolgen bestehen und die Reihenfolge, in der die Tiere sich begegnen, mehr oder weniger zufallsabhängig ist. Insgesamt ist ein Suchbaum also einer linearen Liste vorzuziehen.

b) Geben Sie an, was die Methode liefereEtwas bei Anwendung auf die Beispieldaten aus den Abbildungen 1 und 2 zurückgibt.

Lösung: grsmt / Kontakt grsmt

b) Erläutern Sie die Arbeitsweise der Methode liefereEtwas.

Lösung: Die Methode liefereEtwas erwartet keine Parameter und liefert ein Objekt vom Typ Kontakt zurück (Zeile 1). Falls Kontakte existieren (Zeile 3), werden eine leere Hilfsschlange q aus Suchbäumen und eine mit 0 initialisierte Ganzzahl max angelegt (Zeilen 4 bis 6). Der im Attribut kontakte referenzierte Suchbaum wird an q angehängt (Zeile 7) und eine Schleife mindestens einmal ausgeführt. Diese bricht ab, wenn q leer ist (Zeilen 8 bis 22). Innerhalb der Schleife wird das erste Objekt von q (Suchbaum) als hilf referenziert und aus q entfernt, anschließend wird der Inhalt der Wurzel von hilf (Kontakt) als aktuell referenziert (Zeilen 9 bis 11). Falls die maximale Signalstärke aller der vom aktuell betrachteten Kontakt verwalteten Begegnungen größer als der bisherige maximale Wert max ist, so wird max auf diese maximale Signalstärke gesetzt und die Ergebnisvariable referenziert den aktuell betrachteten Kontakt (Zeilen 12 bis 15). Danach werden der linke bzw. der rechte Teilbaum des aktuell als hilf referenzierten Suchbaums an q angehängt, sofern diese jeweils nicht leer sind (Zeilen 16 bis 21). Am Ende wird der zuletzt als ergebnis referenzierte Kontakt zurückgegeben oder null, falls noch keine Kontakte existieren (Zeilen 2, 3 und 24). Durch die Nutzung der Hilfsschlange q werden die einzelnen Kontakte des Suchbaums gemäß einer Breitensuche Ebene für Ebene traversiert.

b) Erläutern Sie im Sachzusammenhang, welches Ergebnis die Methode liefereEtwas liefert.

Lösung: Im Sachzusammenhang liefert die Methode den Kontakt, mit dem es die engste Begegnung (Begegnung mit der größten Signalstärke) gab, falls bereits Kontakte existieren. Gibt es mehrere Kontakte mit Begegnungen mit der gleichen maximalen Signalstärke, so wird der gemäß der Breitensuche zuerst betrachtete Kontakt zurückgegeben.

c) Entwickeln und erläutern Sie eine algorithmische Vorgehensweise für die Methode liefereBegegnungen.

Lösung: Um alle Begegnungen aller Kontakte hinsichtlich der geforderten Mindest-Signalstärke zu überprüfen, muss der Suchbaum kontakte vollständig traversiert werden. Dies ist z. B. rekursiv nach dem Prinzip in-order möglich. Dazu wird eine private Hilfsmethode implementiert, die die Parameterliste von liefereBegegnungen um einen weiteren Parameter (vom Typ BinarySearchTree mit Inhaltsobjekten vom Typ Kontakt) ergänzt, die von der öffentlichen Methode mit dem zusätzlichen Parameterwert kontakte aufgerufen und deren Rückgabe von dieser zurückgegeben wird. Die private Hilfsmethode erzeugt eine leere Liste, die Objekte der Klasse Begegnung verwaltet. Sofern der übergebene Suchbaum nicht leer ist, geschieht Folgendes: Zunächst wird das Ergebnis des rekursiven Aufrufs der Hilfsmethode für den linken Teilbaum des übergebenen Suchbaums an die Liste angehängt. Danach werden die Begegnungen des Inhalts der Wurzel des übergebenen Suchbaums (Begegnungen des aktuell betrachteten Kontakts) überprüft. Übersteigt die Signalstärke der aktuell betrachteten Begegnung den als pMin übergebenen Wert, wird diese Begegnung hinten an die Liste angehängt. Abschließend wird das Ergebnis des rekursiven Aufrufs der Hilfsmethode für den rechten Teilbaum des übergebenen Suchbaums an die Liste angehängt. Zuletzt wird die erzeugte (ggf. leere) Liste zurückgegeben.

c) Implementieren Sie die Methode liefereBegegnungen entsprechend Ihrer Strategie und der Dokumentation im Anhang.

Lösung: ```java public List<Begegnung> liefereBegegnungen(int pMin) { return liefereBegegnungen(kontakte, pMin); } private List<Begegnung> liefereBegegnungen( BinarySearchTree<Kontakt> pBaum, int pMin) { List<Begegnung> ergebnis = new List<Begegnung>(); if (!pBaum.isEmpty()) { ergebnis.concat(liefereBegegnungen(pBaum.getLeftTree(), pMin)); List<Begegnung> begegnungen = pBaum.getContent().gibBegegnungen(); begegnungen.toFirst(); while (begegnungen.hasAccess()) { Begegnung aktuell = begegnungen.getContent(); if (aktuell.gibSignalstaerke() > pMin) { ergebnis.append(aktuell); } begegnungen.next(); } ergebnis.concat(liefereBegegnungen(pBaum.getRightTree(), pMin)); } return ergebnis; } ```