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

Sachkontext: Automatisierte Verkehrszählung

Damit sich das Verkehrsaufkommen auf Fernstraßen besser beurteilen lässt, finden regelmäßig Verkehrszählungen statt. Im Zuge der Digitalisierung soll dieser Vorgang nun automatisch ablaufen. Eine Kamera und eine passende Bilderkennungssoftware sollen dazu die Ortskürzel (auch Ortskennzeichen genannt) der vorbeifahrenden Kraftfahrzeuge (Kfz) selbstständig identifizieren und zählen. Die Daten werden in einem binären Suchbaum gespeichert, dessen Ordnung sich aus der alphabetischen Reihenfolge der Ortskürzel ergibt.

Die Zählsoftware soll um weitere Merkmale erweitert werden: Für jede Messung sollen der exakte Zeitpunkt sowie die Fahrzeugklasse des Fahrzeugs, das die Zählstelle durchfuhr, festgehalten werden. Bei der Fahrzeugklasse soll unterschieden werden zwischen dem typischen Personenverkehr in PKW einerseits und allen sonstigen, insbesondere größeren Kraftfahrzeugen andererseits (z. B. Bussen, Traktoren und Lastkraftwagen).

Grundlage der Software ist das Implementationsdiagramm, von dem Abbildung 2 einen Ausschnitt zeigt. Die Dokumentation der benutzten Klassen steht im Anhang.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Zaehlung

Ein Objekt dieser Klasse führt die Verkehrszählung automatisiert durch, d. h., es dient zur Erfassung, Verwaltung und Auswertung aller Zählungsdaten.

Zaehlung()

Ein Objekt der Klasse wird initialisiert. Alle notwendigen Rahmenbedingungen zur Durchführung der Zählung sind nach Ausführung des Konstruktors erledigt (z. B. Initialisierung der Datenstrukturen).

void erfasseKfz(String pOrtsKuerzel, char pKfzKlasse)

Wenn ein vorbeifahrendes Kraftfahrzeug erkannt wurde, wird diese Methode aufgerufen. Ihr wird das Ortskürzel des Kraftfahrzeugs als Parameter pOrtsKuerzel übergeben. Der Parameter pKfzKlasse beinhaltet ein Kürzel für die Fahrzeugklasse (vorgesehen sind P für PKW oder S für sonstige Kraftfahrzeuge).

Ist zum übergebenen Ortskürzel bereits ein Knoten im binären Suchbaum verkehrszaehlung enthalten, wird er ermittelt, andernfalls wird ein neuer Knoten mit einem neuen Inhaltsobjekt aus der Klasse OrtsDaten erzeugt und dem Baum hinzugefügt. Der Liste aus Messungen, die durch das Inhaltsobjekt des Knotens verwaltet werden, wird ein neues Objekt der Klasse Messung hinzugefügt, das den aktuellen Zeitstempel und die übergebene Kfz-Klasse enthält.

List<OrtsDaten> ermittleRegionDaten(String[] pRegion)

Die Anfrage liefert eine Liste aus Objekten der Klasse OrtsDaten zurück, deren Ortskürzel aus der durch pRegion näher bestimmten Region stammen. Jedes Element des Felds (Arrays) gibt ein anderes Ortskürzel der Region an.

int ermittleEtwas(Zeitstempel pZ1, Zeitstempel pZ2)

Diese Methode analysiert die Zählungsdaten innerhalb des angegebenen Zeitraums.

Die Klasse OrtsDaten

Ein Objekt dieser Klasse verwaltet alle Messdaten zu einem bestimmten Ortskürzel.

OrtsDaten(String pOrtsKuerzel)

Ein Objekt der Klasse wird initialisiert. Dabei wird das Ortskürzel durch den Parameter pOrtsKuerzel im Klartext übergeben. Die durch dieses Objekt verwaltete Liste der Messungen ist nachher leer.

String gibOrtsKuerzel()

Das Ortskürzel wird zurückgegeben.

int gibAnzahlMessungen()

Die Anzahl der bisher aufgezeichneten Messungen wird zurückgegeben.

List<Messung> gibMessungen()

Die Liste aller Messungen, die zum zugehörigen Ortskürzel gespeichert sind, wird zurückgegeben. Liegen keine Messungen vor, wird eine leere Liste zurückgegeben.

void erfasseMessung(Messung pMessung)

Das als pMessung übergebene Objekt wird an die Liste der Messungen, die durch dieses Objekt verwaltet werden, angehängt.

boolean isLess(OrtsDaten pOrt)

Die Anfrage liefert true zurück, wenn das von diesem Objekt verwaltete Ortskürzel alphabetisch vor demjenigen des Objekts pOrt liegt, sonst false.

boolean isEqual(OrtsDaten pOrt)

Die Anfrage liefert true zurück, wenn das Ortskürzel des Objekts pOrt demjenigen Ortskürzel gleich ist, das durch dieses Objekt verwaltet wird, sonst false.

boolean isGreater(OrtsDaten pOrt)

Die Anfrage liefert true zurück, wenn das von diesem Objekt verwaltete Ortskürzel alphabetisch hinter demjenigen des Objekts pOrt liegt, sonst false.

Die Klasse Messung

Ein Objekt dieser Klasse verwaltet die individuellen Messdaten einer bestimmten Messung zu einem bestimmten Ortskennzeichen.

Messung(char pKfzKlasse)

Ein Objekt dieser Klasse wird erzeugt, das als Kfz-Klasse den durch pKfzKlasse übergebenen Wert und einen Zeitstempel mit dem aktuellen Zeitpunkt enthält. Für pKfzKlasse sind die Werte P für PKW und S für sonstige Kraftfahrzeuge erlaubt.

Zeitstempel gibZeitstempel()

Der Zeitstempel dieser Messung wird zurückgegeben.

char gibKfzKlasse()

Das Kürzel der Kraftfahrzeugklasse zu dieser Messung wird zurückgegeben.

Die Klasse Zeitstempel

Ein Objekt dieser Klasse verwaltet einen sekundengenauen Zeitpunkt.

Zeitstempel()

Ein Zeitstempel mit aktuellem Datum und sekundengenauer Uhrzeit wird erzeugt.

Zeitstempel(int pJahr, int pMonat, int pTag, int pStunde, int pMinute, int pSekunde)

Ein Zeitstempel mit dem durch die Parameter bestimmten Datum und sekundengenauer Uhrzeit wird erzeugt.

boolean liegtInnerhalb(Zeitstempel pVon, Zeitstempel pBis)

Wenn dieser Zeitstempel innerhalb des durch die beiden Zeitstempel pVon und pBis angegebenen Zeitraums liegt, wird true zurückgegeben, sonst false.

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.

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. 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.

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.

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.

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) [8 Punkte]

An einer Zählstelle haben bislang Kraftfahrzeuge mit den Ortskürzeln AC, MS, MS und PB die Messstelle passiert. Der folgende binäre Suchbaum stellt diese Messungen dar:

a.1)

a.2)

Erweitern Sie den binären Suchbaum aus Abbildung 1, wobei die Kamera nun nacheinander die Ortskürzel ST, MS, BI, RS, SO, MS, OB, HSK, PB, DO erfasst.

Zeichnen Sie jeweils den entstehenden Suchbaum nach dem Einfügen der dritten zusätzlichen Messung (nach BI) sowie nach dem Einfügen der letzten zusätzlichen Messung (nach DO).

Teilaufgabe c) [12 Punkte]

Um die Zählungsergebnisse auszuwerten, sollen die erfassten Daten nach verschiedenen Kriterien gefiltert werden. Zunächst sollen die Ortsdaten gesammelt werden, deren Ortskürzel zu einer bestimmten Region gehören. Dafür ist die Methode ermittleRegionDaten zu implementieren. Ihr wird ein Feld (Array) von String-Objekten mit den Ortskürzeln der gewünschten Region übergeben, und sie gibt eine Liste von Objekten der Klasse OrtsDaten zurück.

c.1)

c.2)

public List<OrtsDaten> ermittleRegionDaten(String[] pRegion)

Teilaufgabe d) [12 Punkte]

Die Implementation der Klasse Zaehlung enthält die undokumentierte Methode ermittleEtwas:

1 public int ermittleEtwas(Zeitstempel pZ1, Zeitstempel pZ2) {

2 return ermittleEtwas(verkehrszaehlung, pZ1, pZ2);

3 }

4

5 private int ermittleEtwas(BinarySearchTree<OrtsDaten> pBaum,

6 Zeitstempel pZ1, Zeitstempel pZ2) {

7 int ret = 0;

8 if (!pBaum.isEmpty()) {

9 OrtsDaten aktuell = pBaum.getContent();

10 List<Messung> lmAktuell = aktuell.gibMessungen();

11 lmAktuell.toFirst();

12 while (lmAktuell.hasAccess()) {

13 Zeitstempel zs =

14 lmAktuell.getContent().gibZeitstempel();

15 if (zs.liegtInnerhalb(pZ1, pZ2)) {

16 ret = ret + 1;

17 }

18 lmAktuell.next();

19 }

20 ret = ret + ermittleEtwas(pBaum.getLeftTree(),

21 pZ1, pZ2);

22 ret = ret + ermittleEtwas(pBaum.getRightTree(),

23 pZ1, pZ2);

24 }

25 return ret;

26 }

d)