Aufgabe 2 - Binärbäume und binäre Suchbäume · Abitur NRW Informatik GK · Haupttermin 2021

Ein neu gegründetes Startup in Köln vermietet Elektro-Roller (Scooter). Jeder Scooter besitzt einen GPS-Empfänger und sendet per Internetverbindung jede Minute seine aktuelle Position (Standort) und seinen Batterie-Zustand (Akkuladung) an den Unternehmensserver. Damit sich der Abstand zur Firmenzentrale einfach bestimmen lässt, geben die Scooter ihre Position relativ zur Firmenzentrale an (Koordinatenursprung). Auf dem Server wird die zuletzt gemeldete Position jeweils als Punkt in einem Koordinatensystem abgelegt. Abbildung 1 stellt die momentane Lage in der näheren Umgebung der Firmenzentrale dar.

Die Scooter werden im Unternehmen in einem binären Suchbaum verwaltet. Als Suchschlüssel im Baum dient die eindeutige vierstellige (Serien-)Nummer eines Scooters.

Aktuell setzt das Unternehmen die vier in Abbildung 1 gezeigten Scooter ein. Abbildung 2 zeigt den daraus entstehenden binären Suchbaum.

Die Software des Unternehmens verwaltet neben den Scooter-Daten auch die Daten der Kundinnen und Kunden, die Scooter ausleihen wollen. Vereinfachend wird jede Kundin und jeder Kunde in der Modellierung nur durch eine eindeutige E-Mail-Adresse und eine Kreditkartennummer für die Abrechnung beschrieben.

Grundlage der Software ist der in Abbildung 3 gezeigte Ausschnitt des Implementationsdiagramms.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Scooter

Objekte dieser Klasse verwalten die Daten eines Scooters.

Methode · Beschreibung

Scooter(int pNummer) · Ein Objekt der Klasse wird initialisiert. Die eindeutige Nummer pNummer wird gespeichert.

boolean isEqual(Scooter pComparableContent) · Wenn die eindeutige Nummer des Scooter-Objekts, von dem die Methode aufgerufen wird, gleich der Nummer des Scooter-Objekts pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

boolean isLess(Scooter pComparableContent) · Wenn die eindeutige Nummer des Scooter-Objekts, von dem die Methode aufgerufen wird, kleiner als die Nummer des Scooter-Objekts pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

boolean isGreater(Scooter pComparableContent) · Wenn die eindeutige Nummer des Scooter-Objekts, von dem die Methode aufgerufen wird, größer als die Nummer des Scooter-Objekts pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

int gibNummer() · Die Methode liefert die eindeutige Nummer des Scooters.

int gibAkkuladung() · Die Methode liefert den Batterie-Zustand des Scooters. Der Wert entspricht der Akkuladung in Prozent, d. h., der Wert liegt im Wertebereich 0 (Akku ist leer) bis 100 (Akku ist vollständig aufgeladen).

Kunde gibAusleiher() · Die Methode liefert das Objekt der Klasse Kunde, welcher den Scooter momentan ausgeliehen hat. Ist der Scooter momentan nicht verliehen, so wird null zurückgegeben.

Standort gibStandort() · Die Methode liefert ein Objekt der Klasse Standort, welches die Koordinaten relativ zur Firmenzentrale enthält. Z. B. bedeutet der Standort (-300|400), dass sich der Scooter 300 Meter in westlicher Richtung und 400 Meter in nördlicher Richtung von der Firmenzentrale befindet.

void setzeAkkuladung(int pAkkuladung) · Die Methode verändert den Wert der Akkuladung auf den Wert pAkkuladung. Ist der Wert kleiner als 0 oder größer als 100, so geschieht nichts.

void setzeAusleiher(Kunde pAusleiher) · Die Methode speichert die Daten der Person, die den Scooter momentan ausgeliehen hat. Ist der Parameter pAusleiher gleich null, so ist der Scooter wieder frei und kann von jemand anderem ausgeliehen werden.

void setzeStandort(Standort pStandort) · Die Methode setzt den Standort des Scooters auf pStandort.

Die Klasse ScooterVerwaltung

Objekte dieser Klasse verwalten Scooter sowie Kundinnen und Kunden und ermöglichen die Ausleihe von Scootern.

Methode · Beschreibung

ScooterVerwaltung() · Ein Objekt der Klasse wird initialisiert. Es verwaltet noch keine Scooter und keine Daten von Kundinnen und Kunden.

void ausleihen(String pEMailAdresse, int pScooternummer) · Die Person mit der E-Mail-Adresse pEMailAdresse leiht den Scooter mit der Nummer pScooternummer aus. Dazu speichert das zugehörige Objekt der Klasse Scooter eine Referenz auf das zugehörige Objekt der Klasse Kunde. Sollte keine Kundin und kein Kunde mit der E-Mail-Adresse pEMailAdresse bzw. kein Scooter mit der Nummer pScooternummer existieren, so geschieht nichts. Sollte der Scooter bereits ausgeliehen sein, so geschieht ebenfalls nichts.

Scooter gibScooter(int pScooternummer) · Liefert das Scooter-Objekt mit der (Serien-)Nummer pScooternummer. Falls es kein Scooter-Objekt mit der entsprechenden (Serien-)Nummer gibt, dann wird null zurückgeliefert.

List<Scooter> liefereEtwas(int pWert) · Die Methode wird in Teilaufgabe c) analysiert.

Die Klasse Kunde

Objekte dieser Klasse verwalten die Daten einer Kundin bzw. eines Kunden.

Methode · Beschreibung

Kunde(String pEMailAdresse, String pKreditkartennummer) · Ein Objekt der Klasse wird initialisiert. Die eindeutige E-Mail-Adresse pEMailAdresse der Kundin bzw. des Kunden und die zugehörige Kreditkartennummer pKreditkartennummer werden gespeichert.

String gibEMailAdresse() · Die eindeutige E-Mail-Adresse der Kundin bzw. des Kunden wird zurückgeliefert.

String gibKreditkartennummer() · Die Kreditkartennummer der Kundin bzw. des Kunden wird zurückgeliefert.

Die Klasse Standort

Objekte dieser Klasse verwalten die Koordinaten eines Standorts für Scooter. Die Koordinaten werden relativ zur Firmenzentrale gespeichert, welche sich im Koordinatenursprung befindet.

Methode · Beschreibung

Standort(int pX, int pY) · Ein Objekt der Klasse wird initialisiert. Die Koordinaten (pX|pY) werden im Objekt gespeichert.

int gibX() · Die x-Koordinate des Standorts wird zurückgeliefert. Diese entspricht der Entfernung in westlicher (bei negativem Wert) bzw. in östlicher (bei positivem Wert) Richtung in Metern von der Firmenzentrale.

int gibY() · Die y-Koordinate des Standorts wird zurückgeliefert. Diese entspricht der Entfernung in südlicher (bei negativem Wert) bzw. in nördlicher (bei positivem Wert) Richtung in Metern von der Firmenzentrale.

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.

Methode · Beschreibung

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. Dabei muss durch Überschreiben der drei Vergleichsmethoden isLess, isEqual, isGreater eine eindeutige Ordnungsrelation festgelegt sein.

Für je zwei Objekte c1 und c2 vom Typ ContentType gilt also insbesondere genau eine der drei Aussagen:

c1.isLess(c2) (Sprechweise: c1 ist kleiner als c2)

c1.isEqual(c2) (Sprechweise: c1 ist gleichgroß wie c2)

c1.isGreater(c2) (Sprechweise: c1 ist größer als c2)

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.

Methode · Beschreibung

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.

Methode · Beschreibung

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)

Das Unternehmen verfügt über weitere Scooter, die in den bestehenden Datenbestand aufgenommen werden sollen. Zuerst werden vier Scooter mit den Nummern 4999, 4400, 1000 und 8500 exakt in dieser Reihenfolge in den Suchbaum aus Abbildung 2 eingefügt.

Stellen Sie den Suchbaum, der sich nach dem Einfügen ergibt, grafisch dar.

Stellen Sie den Suchbaum grafisch dar, der sich aus dem Suchbaum mit den acht Suchschlüsseln ergibt, wenn der Scooter mit der Nummer 4671 gestohlen wurde und daher aus dem System entfernt werden muss.

Teilaufgabe c)

Die Klasse ScooterVerwaltung enthält die folgenden Methoden:

1 public List<Scooter> liefereEtwas(int pWert) {

2 return liefereEtwas(pWert, alleScooter);

3 }

4

5 private List<Scooter> liefereEtwas(

6 int pWert, BinarySearchTree<Scooter> pBaum) {

7 List<Scooter> ergebnis = new List<Scooter>();

8 if (!pBaum.isEmpty()) {

9 ergebnis.concat(

10 liefereEtwas(pWert, pBaum.getLeftTree()));

11 Scooter s = pBaum.getContent();

12 if (pWert >= s.gibAkkuladung()) {

13 ergebnis.append(s);

14 }

15 ergebnis.concat(

16 liefereEtwas(pWert, pBaum.getRightTree()));

17 }

18 return ergebnis;

19 } Angenommen, der binäre Suchbaum alleScooter enthält den Suchbaum aus Abbildung 2 mit den Suchschlüsseln der Scooter aus Abbildung 1. Die öffentliche Methode liefereEtwas wird mit dem Parameter pWert = 80 aufgerufen.

Analysieren Sie den Quelltext der beiden Methoden, indem Sie diese auf die Beispieldaten anwenden und die dabei entstehende Rückgabe-Liste ermitteln.

Erläutern Sie, wie die private Methode arbeitet.

Erläutern Sie im Sachkontext, welche Information die öffentliche Methode zurückgibt.

Teilaufgabe e)

Jeden Abend soll kontrolliert werden, ob sämtliche Scooter vorschriftsmäßig abgestellt sind. Dafür setzt das Unternehmen eine Drohne ein, die abends alle Scooter anfliegt und von jedem ein Foto an die Firmenzentrale sendet. Sind alle Scooter fotografiert, kehrt die Drohne zur Firmenzentrale zurück.

Ein Praktikant empfiehlt, die Scooter zuerst aufsteigend nach ihrer Entfernung von der Firmenzentrale zu sortieren und in dieser Ordnung in einer Liste abzulegen.

Anhand dieser Liste könnte die Drohne die Scooter nacheinander anfliegen und fotografieren.

Wenden Sie die Strategie des Praktikanten auf die Beispieldaten der Scooter aus Abbildung 1 an, indem Sie ermitteln, in welcher Reihenfolge die Scooter angeflogen werden.

Entwickeln Sie eine Strategie für einen Algorithmus, der eine derart sortierte Liste aller im Baum alleScooter gespeicherten Scooter-Objekte erzeugt.

Begründen Sie anhand eines selbst gewählten Beispiels im Sachkontext, weshalb die Strategie des Praktikanten nicht stets eine optimale Flugroute liefert.