Aufgabe 2 - Binäre Suchbäume · Abitur NRW Informatik LK · Haupttermin 2021

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

Das Unternehmen verwaltet die Scooter in einem binären Suchbaum. 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. Der daraus entstehende binäre Suchbaum ist in Abbildung 2 zu sehen.

Die Software des Unternehmens verwaltet außer den Scooter-Daten auch die Daten der Kundinnen und Kunden, die einen Scooter mieten wollen. Vereinfachend ist modelliert, dass jede Kundin und jeder Kunde nur durch eine eindeutige E-Mail-Adresse sowie eine Kreditkartennummer für die Abrechnung beschrieben wird.

Grundlage der Softwareentwicklung 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 / Konstruktor · 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, welches 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 / Konstruktor · Beschreibung

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

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<Kunde> ermittleWarnliste(int pDistanz) · Die Methode liefert eine Liste aller Kundinnen und Kunden, die sich mit ihrem ausgeliehenen Scooter um mehr als pDistanz Meter Luftlinie von der Firmenzentrale entfernt haben. Die Firmenzentrale befindet sich im Standort (0|0). Gibt es keine Kundin und keinen Kunden, die bzw. der sich zu weit entfernt hat, oder ist der Parameter pDistanz < 0, so wird eine leere Liste zurückgegeben. Scooter, die momentan nicht ausgeliehen wurden, sich aber in größerer Distanz befinden, werden nicht berücksichtigt, weil es keine Person gibt, an den eine Warnmeldung verschickt werden könnte.

List<Scooter> ermittleEtwas(List<Scooter> pScooterSammlung) · Die Methode wird in Teilaufgabe c) analysiert.

Die Klasse Kunde

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

Methode / Konstruktor · 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 / Konstruktor · Beschreibung

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

int liefereDistanz(Standort pOrt) · Die auf volle Meter abgerundete Distanz (Luftlinie in Metern) zwischen dem gespeicherten Ort und dem durch pOrt referenzierten Ort wird zurückgegeben. Sollte pOrt den Wert null haben, so wird der Wert 0 zurückgegeben.

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 / Konstruktor · 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 der 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. 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 der Liste 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 (siehe Dokumentation des Interfaces) eine eindeutige Ordnungsrelation festgelegt sein. Die Objekte der Klasse ContentType sind damit vollständig geordnet. 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 / Konstruktor · 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.

a)

Weitere Scooter des Unternehmens sollen in den bestehenden Datenbestand aufgenommen werden. Als Erstes werden die vier Scooter mit den Nummern 4999, 4400, 1000 und 8500 genau in dieser Reihenfolge in den Suchbaum aus Abbildung 2 eingefügt.

Stellen Sie den Suchbaum, der nach dem Einfügen vorliegt, 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.

d)

Wenn Scooter sehr weit von der Firmenzentrale entfernt sind, kann die Drohne sie abends nicht mehr gut anfliegen. Daher sollen Kundinnen und Kunden, die sich z. B. mehr als 10 000 Meter von der Firmenzentrale entfernen, per hinterlegter E-Mail-Adresse gewarnt werden.

Um die Liste aller Personen zu bestimmen, die eine solche Warnmeldung bekommen sollen, bietet die Klasse ScooterVerwaltung die Methode ermittleWarnliste an, die folgenden Methodenkopf hat:

public List<Kunde> ermittleWarnliste(int pDistanz)

Die Dokumentation der Methode befindet sich in der Anlage.

Entwickeln Sie eine Strategie für den Algorithmus dieser Methode.

Implementieren Sie die Methode gemäß der Dokumentation.

e)

Ein Praktikant bemerkt, dass die Entfernung eines Scooters zur Firmenzentrale in mehreren Zusammenhängen eine zentrale Information ist, und nennt dafür zwei Beispiele:

Bei entliehenen Scootern spielt die Entfernung etwa beim Versenden von Warnmeldungen für zu weit entfernte Scooter eine Rolle.

Bei nicht entliehenen Scootern ist sie hingegen ein wichtiges Kriterium für den Flug der Drohne, welche kontrolliert, ob vorschriftsmäßig geparkt wurde.

Deshalb regt er an, im binären Suchbaum die Entfernung zwischen Scooter und Firmenzentrale als Sortierkriterium zu nutzen.