Aufgabe 2 - Binäre Suchbäume · Abitur NRW Informatik GK · Nachtermin 2023

Aufgabenstellung: Lagerverwaltung des Onlineshops Infozon

Der Onlineshop Infozon bietet eine große Zahl von Artikeln an und ist in den vergangenen Jahren stark gewachsen. Deshalb braucht das Unternehmen eine neue Software zur Lagerverwaltung. Die IT-Abteilung hat sich aus verschiedenen Gründen dafür entschieden, die Artikel in einem binären Suchbaum abzulegen, der nach der Artikelnummer geordnet ist.

Zu jedem Artikel wird festgehalten, in welchem Regalfach sich wie viele noch verkäufliche Exemplare befinden. Jedes Regalfach darf nur Exemplare eines einzigen Artikels enthalten. Auch wenn ein Regalfach leer geworden ist, bleibt es in der Lagerverwaltung dem Artikel zugeordnet.

Der Lagerbestand enthält die folgenden Beispieldaten:

Ein Ausschnitt der Modellierung ist als Implementationsdiagramm wiedergegeben:

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Lagerverwaltung

Objekte der Klasse Lagerverwaltung verwalten den Bestand von Artikeln in Fächern.

Auszug aus der Dokumentation der Klasse Lagerverwaltung

Lagerverwaltung()

Ein Lagerverwaltungsobjekt wird initialisiert. Das Lager ist leer.

Artikel ermittle(int pArtikelnr)

Die Anfrage liefert für die Artikelnummer pArtikelnr das entsprechende Artikelobjekt. Falls zu pArtikelnr kein Artikelobjekt existiert, dann wird null zurückgeliefert.

void fuegeHinzu(Artikel pArtikel)

Falls der Artikel mit der gleichen Artikelnummer im Lager noch nicht existiert, wird dieser der Lagerverwaltung hinzugefügt.

void erhoeheBestand(Artikel pArtikel, int pFachnr, int pAnzahl)

Falls in der Lagerverwaltung ein Artikel mit der Artikelnummer pArtikel existiert, dann wird in dem Fach mit der Fachnummer pFachnr der Bestand um pAnzahl erhöht. Falls das Fach nicht existiert, dann wird dieses mit dem Bestand pAnzahl angelegt.

void entnimm(Artikel pArtikel, int pFachnr, int pAnzahl)

Falls in der Lagerverwaltung ein Artikel mit der Artikelnummer pArtikel existiert und zu dem Artikel das Fach mit der Fachnummer pFachnr existiert und der Bestand in diesem Fach größer gleich pAnzahl ist, dann wird der Bestand in diesem Fach um pAnzahl verringert.

Die Klasse Artikel

Objekte der Klasse Artikel verwalten die Informationen über einen Artikel und seine Fächer mit Bestandsangaben.

Auszug aus der Dokumentation der Klasse Artikel

Artikel(int pNr, String pBezeichnung)

Ein Artikelobjekt mit der Artikelnummer pNr und der Artikelbezeichnung pBezeichnung wird initialisiert.

int gibNr()

Die Artikelnummer wird zurückgeliefert.

String gibBezeichnung()

Die Artikelbezeichnung wird zurückgeliefert.

List<Fach> gibFaecher()

Eine Liste der Fächer für diesen Artikel wird zurückgeliefert.

boolean isEqual(Artikel pArtikel)

Wenn die Artikelnummer gleich der Artikelnummer des Artikels pArtikel ist, dann wird true zurückgeliefert und sonst false.

boolean isLess(Artikel pArtikel)

Wenn die Artikelnummer kleiner ist als die Artikelnummer des Artikels pArtikel, dann wird true zurückgeliefert und sonst false.

boolean isGreater(Artikel pArtikel)

Wenn die Artikelnummer größer ist als die Artikelnummer des Artikels pArtikel, dann wird true zurückgeliefert und sonst false.

void fuegeHinzu(int pFachnr, int pAnzahl)

Falls das Fach mit der Fachnummer pFachnr für diesen Artikel existiert, dann wird der Bestand um pAnzahl erhöht.

Falls das Fach mit der Fachnummer pFachnr für diesen Artikel nicht existiert, dann wird ein neues Fach mit der Fachnummer pFachnr und dem Bestand pAnzahl angelegt.

Die Klasse Fach

Objekte der Klasse Fach verwalten die Informationen über die Fachnummer und den Bestand in diesem Fach. Die Fachnummer ist für jedes Fach eindeutig.

Auszug aus der Dokumentation der Klasse Fach

Fach(int pFachnr, int pBestand)

Ein Fachobjekt mit der Fachnummer pFachnr und dem Bestand pBestand wird initialisiert.

int gibFachnr()

Die Fachnummer wird zurückgeliefert.

int gibBestand()

Der Bestand wird zurückgeliefert.

void setzeBestand(int pBestand)

Der Bestand wird auf den Wert von pBestand gesetzt.

Die generische Klasse List

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

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.

Dokumentation der generischen 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.

Das Interface ComparableContent gibt folgende implizit abstrakte Methoden vor:

Auszug aus der 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)

a.1)

Geben Sie eine Reihenfolge an, in der die Artikel des in Abbildung 1 gezeigten Baums eingefügt worden sein können.

a.2)

Stellen Sie den Suchbaum dar, der sich ergibt, wenn die neuen Artikel "Tennisschläger" [Artikelnr: 5005; Fachnr: 10, Bestand: 7] und "Tennisball" [Artikelnr: 3000; Fachnr: 81, Bestand: 3, Fachnr: 82, Bestand: 10] in genau dieser Reihenfolge in den bestehenden Suchbaum eingefügt werden.

Hinweis: Nutzen Sie zur Bearbeitung die Vorlage in der Anlage oder fertigen Sie eine Skizze auf Papier an.

a.3)

Geben Sie bezogen auf den dargestellten Kontext einen wichtigen Vorteil an, den ein Suchbaum im Vergleich zu einer nach Artikelnummern sortierten Liste bietet.

Teilaufgabe c)

Der Quellcode der Klasse Lagerverwaltung enthält die folgenden Methoden, die weder dokumentiert noch kommentiert sind:

public List<Artikel> ermittleEtwas(int pMindestbestand) {

return ermittleEtwas(lager, pMindestbestand);}private List<Artikel> ermittleEtwas(

BinarySearchTree<Artikel> pBaum, int pMindestbestand) {

List<Artikel> ergebnis = new List<Artikel>();

if (!pBaum.isEmpty()) {

ergebnis = ermittleEtwas(pBaum.getLeftTree(), pMindestbestand);

Artikel aktuellerArtikel = pBaum.getContent();

List<Fach> liste = aktuellerArtikel.gibFaecher();

int gesamtbestand = 0;

liste.toFirst();

while (liste.hasAccess()) {

gesamtbestand = gesamtbestand + liste.getContent().gibBestand();

liste.next();

}

if (gesamtbestand < pMindestbestand) {

ergebnis.append(aktuellerArtikel);

}

List<Artikel> rechts = ermittleEtwas(pBaum.getRightTree(), pMindestbestand);

ergebnis.concat(rechts);

}

return ergebnis;} Die öffentliche Methode wird mit dem Parameterwert pMindestbestand = 20 aufgerufen. Dabei entspricht der Suchbaum lager dem Suchbaum aus Abbildung 1.

c.1)

Analysieren Sie die beiden Methoden, indem Sie diese auf die Beispieldaten anwenden, dabei die Rückgabe ermitteln und angeben, in welcher Reihenfolge die Artikel des Baums besucht wurden.

c.2)

Erläutern Sie im Sachzusammenhang, welche Information die öffentliche Methode liefert.