Aufgabe 2 - Binärbäume · Abitur NRW Informatik GK · Nachtermin 2022

Aufgabenstellung

Im Nationalpark Wildlife teilen sich mehrere Tierarten ein weitläufiges Freigelände. Die Parkleitung will untersuchen, wie die Tiere miteinander in Kontakt treten. Hierfür tragen die Tiere Halsbänder, die Begegnungen mit anderen Tieren technisch erfassen und verwalten können.

Jedes Halsband sendet in regelmäßigen Zeitabständen ein Signal mit einem eindeutigen individuellen Schlüssel aus fünf Zeichen. Empfängt ein Halsband das Signal eines anderen Halsbands, kommt eine sogenannte Begegnung zustande. Bei dieser werden der mit dem Signal übertragene Schlüssel, die Stärke des Signals (z. B. zur Ermittlung des Abstands der beiden Tiere) und der Zeitpunkt der Begegnung lokal auf dem empfangenden Halsband gespeichert.

Empfängt ein Halsband einen bestimmten Schlüssel zum ersten Mal, wird für diesen zusätzlich ein sogenannter Kontakt angelegt. Dieser verwaltet alle Begegnungen mit dem gleichen Schlüssel. Existiert ein Kontakt zu einem bestimmten Schlüssel, so gibt es bereits mindestens eine Begegnung mit dem Halsband, das diesen Schlüssel versendet.

Die Begegnungen eines Kontakts werden aufsteigend nach ihrem Zeitpunkt sortiert. Die Kontakte werden nach dem Schlüssel alphabetisch sortiert in einem Suchbaum verwaltet.

Zur Überprüfung der Funktionsfähigkeit werden die Halsbänder zunächst einen Tag lang in einem kleineren Gehege an einigen Erdmännchen des Parks getestet. Zum Zeitpunkt der Aktivierung sind auf den Halsbändern zunächst weder Kontakte noch Begegnungen gespeichert. Das Halsband eines Erdmännchens erfasst während des Tests Begegnungen in der in Abbildung 1 angegebenen Reihenfolge. Abbildung 2 zeigt den Suchbaum mit allen Kontakten (dargestellt über ihren Schlüssel und die Anzahl der zugehörigen Begegnungen), der sich bei der Verarbeitung der Begegnungen aus Abbildung 1 ergibt.

Nr.

Schlüssel

Signalstärke

Zeitpunkt

1 · ncgde · 132 · 2022-03-19 15:54

2 · grsmt · 154 · 2022-03-19 16:21

3 · grsmt · 46 · 2022-03-19 16:23

4 · bdsuw · 113 · 2022-03-19 16:27

5 · pwagb · 21 · 2022-03-19 16:33

6 · mkwda · 78 · 2022-03-19 16:34

7 · ncgde · 103 · 2022-03-19 16:35

8 · mkwda · 142 · 2022-03-19 16:39

9 · wrlyr · 69 · 2022-03-19 17:02

Abbildung 1: Begegnungen des Halsbands eines Erdmännchens

Abbildung 4 zeigt einen Ausschnitt aus dem Implementationsdiagramm des Softwaresystems der Halsbänder.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Halsband

Objekte der Klasse Halsband verwalten alle Begegnungen mit anderen Halsbändern in den hierzu angelegten Kontakten. Jedes Objekt dieser Klasse bzw. jedes Halsband entspricht jeweils genau einem Tier.

Ausschnitt aus der Dokumentation der Klasse Halsband

Halsband(String pSchluessel)

Ein Objekt der Klasse wird initialisiert. Zunächst sind weder Kontakte noch Begegnungen gespeichert, der Suchbaum ist leer. Das Halsband versendet in regelmäßigen Zeitabständen Signale mit dem individuellen Schlüssel pSchluessel.

void verarbeiteNeueBegegnung(Begegnung pBegegnung)

Die Methode fügt die Begegnung pBegegnung dem zugehörigen Kontakt hinzu. Falls kein entsprechender Kontakt existiert, wird dieser zunächst erstellt und dem Suchbaum hinzugefügt. Falls pBegegnung == null ist, geschieht nichts.

private List<Begegnung> liefereEtwas(BinarySearchTree<Kontakt> pBaum, int pZahl)

Diese Methode soll in Aufgabenteil c) analysiert werden.

Die Klasse Kontakt

Objekte der Klasse Kontakt verwalten alle Begegnungen, die mit dem gleichen Schlüssel gekennzeichnet sind. Die Begegnungen liegen nach dem Zeitpunkt aufsteigend sortiert vor, zu dem die zugehörigen Signale empfangen wurden. Die Klasse implementiert das Interface ComparableContent.

Ausschnitt aus der Dokumentation der Klasse Kontakt

Kontakt(String pSchluessel)

Ein neuer Kontakt zum erstmalig empfangenen Schlüssel pSchluessel wird initialisiert. Die Liste der Begegnungen ist anfangs leer.

String gibSchluessel()

Die Anfrage liefert den Schlüssel des Kontakts.

List<Begegnung> gibBegegnungen()

Die Anfrage liefert eine neue Liste aller Begegnungsobjekte des Kontakts. Diese sind aufsteigend nach dem Zeitpunkt, zu dem die zugehörigen Signale empfangen wurden, sortiert.

void fuegeBegegnungHinzu(Begegnung pBegegnung)

Die Begegnung pBegegnung wird der Liste der verwalteten Begegnungen unter Beachtung des Sortierkriteriums hinzugefügt.

boolean isGreater(Kontakt pKontakt)

Die Anfrage liefert den Wert true, wenn der eigene Schlüssel lexikographisch größer als der Schlüssel des Kontakts pKontakt ist, sonst liefert sie den Wert false.

boolean isEqual(Kontakt pKontakt)

Die Anfrage liefert den Wert true, wenn der eigene Schlüssel und der Schlüssel des Kontakts pKontakt lexikographisch gleich sind, sonst liefert sie den Wert false.

boolean isLess(Kontakt pKontakt)

Die Anfrage liefert den Wert true, wenn der eigene Schlüssel lexikographisch kleiner als der Schlüssel des Kontakts pKontakt ist, sonst liefert sie den Wert false.

Die Klasse Begegnung

Objekte der Klasse Begegnung verwalten den von einem empfangenen Signal übertragenen Schlüssel, die Stärke des Signals und den Zeitpunkt des Empfangs. Der Zeitpunkt, zu dem das Signal empfangen wird, liegt als Zeichenkette in der Form JJJJ-MM-TT HH:MM vor (z. B. 2022-03-19 15:54).

Ausschnitt aus der Dokumentation der Klasse Begegnung

Begegnung(String pSchluessel, int pSignalstaerke, String pZeitpunkt)

Eine neue Begegnung mit dem Halsband, das den Schlüssel pSchluessel versendet, wird initialisiert. Das zugehörige Signal wird zum Zeitpunkt pZeitpunkt mit der Signalstärke pSignalstaerke empfangen.

String gibSchluessel()

Die Anfrage liefert den Schlüssel der Begegnung.

int gibSignalstaerke()

Die Anfrage liefert die Signalstärke der Begegnung.

String gibZeitpunkt()

Die Anfrage liefert den Zeitpunkt der Begegnung.

Die generische Klasse List<ContentType>

Objekte der generischen Klasse List verwalten beliebig viele, linear angeordnete Objekte vom Typ ContentType. Auf höchstens ein Listenobjekt, aktuelles Objekt genannt, kann jeweils zugegriffen werden. Wenn eine Liste leer ist, vollständig durchlaufen wurde oder das aktuelle Objekt am Ende der Liste gelöscht wurde, gibt es kein aktuelles Objekt. Das erste oder das letzte Objekt einer Liste kann durch einen Auftrag zum aktuellen Objekt gemacht werden. Außerdem kann das dem aktuellen Objekt folgende Listenobjekt zum neuen aktuellen Objekt werden. Das aktuelle Objekt kann gelesen, verändert oder gelöscht werden. Außerdem kann vor dem aktuellen Objekt ein Listenobjekt eingefügt werden.

Dokumentation der Klasse List<ContentType>

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

Die Anfrage liefert den Wert true, wenn die Liste keine Objekte enthält, sonst liefert sie den Wert false.

boolean hasAccess()

Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie den Wert false.

void next()

Falls die Liste nicht leer ist, es ein aktuelles Objekt gibt und dieses nicht das letzte Objekt der Liste ist, wird das dem aktuellen Objekt in der Liste folgende Objekt zum aktuellen Objekt, andernfalls gibt es nach Ausführung des Auftrags kein aktuelles Objekt, d. h., hasAccess() liefert den Wert false.

void toFirst()

Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

void toLast()

Falls die Liste nicht leer ist, wird das letzte Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

ContentType getContent()

Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird das aktuelle Objekt zurückgegeben. Andernfalls (hasAccess() == false) gibt die Anfrage den Wert null zurück.

void setContent(ContentType pContent)

Falls es ein aktuelles Objekt gibt (hasAccess() == true) und pContent ungleich null ist, wird das aktuelle Objekt durch pContent ersetzt. Sonst bleibt die Liste unverändert.

void append(ContentType pContent)

Ein neues Objekt pContent wird am Ende der Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Wenn die Liste leer ist, wird das Objekt pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt (hasAccess() == false). Falls pContent gleich null ist, bleibt die Liste unverändert.

void insert(ContentType pContent)

Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird ein neues Objekt pContent vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt gibt (hasAccess() == false), wird pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt (hasAccess() == false). Falls es kein aktuelles Objekt gibt (hasAccess() == false) und die Liste nicht leer ist oder pContent == null ist, bleibt die Liste unverändert.

void concat(List<ContentType> pList)

Die Liste pList wird an die Liste angehängt. Anschließend wird pList eine leere Liste. Das aktuelle Objekt bleibt unverändert. Falls es sich bei der Liste und pList um dasselbe Objekt handelt, pList == null oder eine leere Liste ist, bleibt die Liste unverändert.

void remove()

Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird das aktuelle Objekt gelöscht und das Objekt hinter dem gelöschten Objekt wird zum aktuellen Objekt. Wird das Objekt, das am Ende der Liste steht, gelöscht, gibt es kein aktuelles Objekt mehr (hasAccess() == false). Wenn die Liste leer ist oder es kein aktuelles Objekt gibt (hasAccess() == false), bleibt die Liste unverändert.

Die generische Klasse BinarySearchTree<ContentType extends ComparableContent<ContentType>>

Mithilfe der generischen Klasse BinarySearchTree können beliebig viele Objekte des Typs ContentType in einem Binärbaum (binärer Suchbaum) entsprechend einer Ordnungsrelation verwaltet werden. Ein Objekt der Klasse BinarySearchTree stellt entweder einen leeren Baum dar oder verwaltet ein Inhaltsobjekt vom Typ ContentType sowie einen linken und einen rechten Teilbaum, die ebenfalls Objekte der Klasse BinarySearchTree sind. Die Klasse der Objekte, die in dem Suchbaum verwaltet werden sollen, muss das generische Interface ComparableContent implementieren.

Die Objekte der Klasse ContentType sind damit vollständig geordnet. Alle Objekte im linken Teilbaum sind kleiner als das Inhaltsobjekt des Binärbaumes. Alle Objekte im rechten Teilbaum sind größer als das Inhaltsobjekt des Binärbaumes. Diese Bedingung gilt auch in beiden Teilbäumen.

Dokumentation der Klasse BinarySearchTree<ContentType extends ComparableContent<ContentType>>

BinarySearchTree()

Der Konstruktor erzeugt einen leeren Suchbaum.

boolean isEmpty()

Diese Anfrage liefert den Wahrheitswert true, wenn der Suchbaum leer ist, sonst liefert sie den Wert false.

void insert(ContentType pContent)

Falls bereits ein Objekt in dem Suchbaum vorhanden ist, das gleichgroß ist wie pContent, passiert nichts. Andernfalls wird das Objekt pContent entsprechend der Ordnungsrelation in den Baum eingeordnet. Falls der Parameter null ist, ändert sich nichts.

ContentType search(ContentType pContent)

Falls ein Objekt im binären Suchbaum enthalten ist, das gleichgroß ist wie pContent, liefert die Anfrage dieses, ansonsten wird null zurückgegeben. Falls der Parameter null ist, wird null zurückgegeben.

void remove(ContentType pContent)

Falls ein Objekt im binären Suchbaum enthalten ist, das gleichgroß ist wie pContent, wird dieses entfernt. Falls der Parameter null ist, ändert sich nichts.

ContentType getContent()

Diese Anfrage liefert das Inhaltsobjekt des Suchbaumes. Wenn der Suchbaum leer ist, wird null zurückgegeben.

BinarySearchTree<ContentType> getLeftTree()

Diese Anfrage liefert den linken Teilbaum des binären Suchbaumes. Der binäre Suchbaum ändert sich nicht. Wenn er leer ist, wird null zurückgegeben.

BinarySearchTree<ContentType> getRightTree()

Diese Anfrage liefert den rechten Teilbaum des Suchbaumes. Der Suchbaum ändert sich nicht. Wenn er leer ist, wird null zurückgegeben.

Das generische Interface ComparableContent<ContentType>

Das generische Interface ComparableContent muss von Klassen implementiert werden, deren Objekte in einen Suchbaum (BinarySearchTree) eingefügt werden sollen. Die Ordnungsrelation wird in diesen Klassen durch Überschreiben der drei implizit abstrakten Methoden isGreater, isEqual und isLess festgelegt.

Dokumentation des Interfaces ComparableContent<ContentType>

boolean isGreater(ContentType pComparableContent)

Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gewünschten Ordnungsrelation größer als das Objekt pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

boolean isEqual(ContentType pComparableContent)

Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gewünschten Ordnungsrelation gleich dem Objekt pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

boolean isLess(ContentType pComparableContent)

Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gewünschten Ordnungsrelation kleiner als das Objekt pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

Teilaufgabe a)

In Abbildung 3 sind die Begegnungen dargestellt, die das Halsband eines weiteren Erdmännchens am Testtag aufgezeichnet hat.

a.1)

Geben Sie an, welche Kontakte beim Verarbeiten der Begegnungen aus Abbildung 3 neu angelegt werden und in welcher Reihenfolge sie in den Suchbaum eingefügt werden.

a.2)

Stellen Sie den Suchbaum, der sich nach der Verarbeitung sämtlicher Begegnungen aus Abbildung 3 ergibt, samt aller darin enthaltenen Kontakte dar (mit Schlüssel und Anzahl der jeweils zugehörigen Begegnungen).

a.3)

Beschreiben Sie in allgemeiner Form, wie sich ein Element in einen Suchbaum einfügen lässt.

Teilaufgabe b)

Die Methode verarbeiteNeueBegegnung der Klasse Halsband ordnet eine neue Begegnung entsprechend der Dokumentation im Anhang einem schon vorhandenen oder neu anzulegenden Kontakt zu. Ihr Methodenkopf lautet:

public void verarbeiteNeueBegegnung(Begegnung pBegegnung) b.1)

Entwickeln und erläutern Sie eine algorithmische Vorgehensweise für die Methode verarbeiteNeueBegegnung.

b.2)

Implementieren Sie die Methode verarbeiteNeueBegegnung entsprechend Ihrer Strategie und der Dokumentation im Anhang.

Teilaufgabe c)

Die private Methode liefereEtwas der Klasse Halsband ist undokumentiert und entstand in einer frühen Entwicklungsphase der Halsbänder. Im Hinblick auf das nächste Update will der Park prüfen, ob die Methode sinnvoll zu neuen Funktionen beitragen kann oder endgültig gelöscht werden sollte.

1 private List<Begegnung> liefereEtwas(

2 BinarySearchTree<Kontakt> pBaum, int pZahl) {

3 List<Begegnung> ergebnis = new List<Begegnung>();

4 if (!pBaum.isEmpty()) {

5 ergebnis.concat(liefereEtwas(pBaum.getLeftTree(),

6 pZahl));

7

8 List<Begegnung> begegnungen

9 = pBaum.getContent().gibBegegnungen();

10 begegnungen.toFirst();

11 while (begegnungen.hasAccess()) {

12 Begegnung aktuell = begegnungen.getContent();

13 if (aktuell.gibSignalstaerke() > pZahl) {

14 ergebnis.append(aktuell);

15 }

16 begegnungen.next();

17 }

18

19 ergebnis.concat(liefereEtwas(pBaum.getRightTree(),

20 pZahl));

21 }

22 return ergebnis;

23 } Die Methode wird auf die Beispieldaten des Testtages aus den Abbildungen 1 und 2 angewendet. Als Argument für den Parameter pBaum wird der Suchbaum aus Abbildung 2 übergeben, für den Parameter pZahl der Wert 100.

c.1)

Analysieren Sie, wie die Methode liefereEtwas arbeitet, und stellen Sie den Inhalt der Liste dar, die bei Anwendung mit den oben genannten Parameterwerten zurückgegeben wird.

Tragen Sie die Begegnungen in der Reihenfolge ein, in der sie in der zurückgegebenen Liste stehen:

Schlüssel · Signalstärke · Zeitpunkt

c.2)

Erläutern Sie, wie die Methode liefereEtwas funktioniert.

c.3)

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