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

Sachkontext: Musikverwaltung mit Hashtags für DJ P.J.

Peter Johann tritt als beliebter Discjockey („DJ P.J.“) auf. Zu seinem Erfolg trägt bei, dass er die Stücke für seine Auftritte weniger nach Titel oder Interpret auswählt, sondern vor allem nach deren Beschreibungen und Merkmalen. Dazu nutzt er eine von ihm selbst entwickelte Software, die alle Musikstücke über sogenannte Hashtags verwaltet. Ein Hashtag ist ein Schlagwort, das ein Musikstück genauer charakterisiert. Jedem Musikstück ist mindestens ein Hashtag zugewiesen. Ein Hashtag beginnt stets mit genau einem Doppelkreuz (#), darauf folgt das beschreibende Schlagwort, das ausschließlich Buchstaben und Ziffern enthalten darf. Gültige Hashtags sind zum Beispiel #Rock, #Blues, #HipHop, #Uptempo140 oder #ChaChaCha, nicht aber #Rock#*Pop!.

Die Hashtags werden in einem binären Suchbaum verwaltet.

Peter hat den Entwurf seiner Software in Abbildung 1 festgehalten und dabei berücksichtigt, dass zu einem Hashtag mehrere Musikstücke gehören können.

Anlage: Beispieldaten

Der Suchbaum bibliothek der Klasse Musikverwaltung habe folgenden Inhalt:

Unter den im Suchbaum verwalteten Hashtags seien folgende Musikstücke (hier nur durch ihren eindeutigen Titel angegeben) verzeichnet:

Hashtag · Titel der Musikstücke

#Discofox · • Jodelecho

• Party geht immer

• Tausend Tage Party

• Tausendmal ganz egal

#Mallorca · • Tanzen im Sand

• Tausend Tage Party

• Tausendmal ganz egal

#Oktoberfest · • Almdudl

• Alphornblasn

• Jodelecho

#Party · • Almdudl

• Alphornblasn

• Party geht immer

• Tausend Tage Party

#Schlager · • Tausendmal tanzen

• Party geht immer

• Tanzen im Sand

• Tausend Tage Party

• Tausendmal ganz egal

#Tausend · • Tausendmal tanzen

• Tausend Tage Party

• Tausendmal ganz egal

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Musikverwaltung

Objekte dieser Klasse verwalten alle Musikstücke und Hashtags einer Musikbibliothek. Ein und dasselbe Musikstück, repräsentiert durch genau ein Objekt der Klasse Musikstueck, kann mehreren Hashtags gleichzeitig zugeordnet sein.

Ausschnitt aus der Dokumentation der Klasse Musikverwaltung

Musikverwaltung()

Eine Musikverwaltung mit einer leeren Bibliothek wird initialisiert.

void fuegeStueckHinzu(Musikstueck pMusikstueck, Hashtag pHashtag)

Der Bibliothek wird das Stück pMusikstueck unter dem Hashtag pHashtag hinzugefügt. Ist das (identische) Objekt bereits in der zugehörigen Musikstück-Liste enthalten, geschieht nichts.

List<Hashtag> liefereHashtags(String pSubstring)

Die Methode liefert eine Liste aller Hashtag-Objekte zurück, deren Zeichenkette den String pSubstring enthält.

List<Musikstueck> liefereEtwas(List<Hashtag> pHashtags)

Diese Methode wird im Rahmen von Aufgabenteil c) analysiert.

Die Klasse Hashtag

Objekte dieser Klasse verwalten die Zeichenkette des Hashtags und alle Musikstücke, die diesem Hashtag zugeordnet sind.

Ausschnitt aus der Dokumentation der Klasse Hashtag

Hashtag(String pZeichenkette)

Ein neues Hashtag-Objekt für das übergebene Hashtag pZeichenkette wird initialisiert. Die Liste der verwalteten Musikstücke ist zu Beginn leer.

String gibZeichenkette()

Die Zeichenkette des Hashtags, das durch dieses Objekt repräsentiert wird, wird als String zurückgegeben.

List<Musikstueck> gibStuecke()

Eine Liste aller Musikstücke, die diesem Hashtag zugeordnet sind, wird zurückgegeben.

void fuegeStueckHinzu(Musikstueck pMusikstueck)

Das übergebene Stück pMusikstueck wird in die Liste der diesem Hashtag-Objekt zugeordneten Stücke aufgenommen. Die Liste ist nachher alphabetisch aufsteigend sortiert. Sollte pMusikstueck schon in der Liste vorhanden sein, geschieht nichts.

boolean isEqual(Hashtag pAnderer)

Wenn die Zeichenkette des Hashtag-Objekts, von dem die Methode aufgerufen wird, gleich der Zeichenkette des Hashtag-Objekts pAnderer ist, wird true geliefert, sonst false.

boolean isLess(Hashtag pAnderer)

Wenn die Zeichenkette des Hashtag-Objekts, von dem die Methode aufgerufen wird, alphabetisch aufsteigend vor der Zeichenkette des Hashtag-Objekts pAnderer liegt, wird true geliefert, sonst false.

boolean isGreater(Hashtag pAnderer)

Wenn die Zeichenkette des Hashtag-Objekts, von dem die Methode aufgerufen wird, alphabetisch aufsteigend hinter der Zeichenkette des Hashtag-Objekts pAnderer liegt, wird true geliefert, sonst false.

Die Klasse Musikstueck

Objekte dieser Klasse modellieren ein Musikstück, bestehend aus Titel und Dauer.

Dokumentation der Klasse Musikstueck

Musikstueck(String pTitel, int pDauer)

Ein neues Musikstueck-Objekt wird initialisiert. Dem Objekt wird der übergebene Titel pTitel und die Dauer pDauer in Sekunden zugeordnet.

String gibTitel()

Der Titel des Musikstücks wird zurückgegeben.

int gibDauer()

Die Dauer des Musikstücks in Sekunden wird zurückgegeben.

Die Klasse String

Objekte dieser Klasse verwalten eine Zeichenkette.

Ausschnitt aus der Dokumentation der Klasse String

String(String pString)

Ein neues String-Objekt wird initialisiert. Dem Objekt ist nachher eine Kopie der durch pString übergebenen Zeichenkette zugeordnet.

int indexOf(String pStr)

Gibt den Index des ersten Vorkommens der angegebenen Teilzeichenkette pStr innerhalb der durch dieses Objekt verwalteten Zeichenkette zurück. Kommt pStr nicht darin vor, wird -1 zurückgegeben.

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:

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.

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.

Teilaufgabe a)

Die folgenden Hashtags werden nacheinander in der genannten Reihenfolge in einen anfangs leeren binären Suchbaum eingetragen:

1. #LoungeJazz 2. #Eminem 3. #Metal 4. #House

5. #Queen 6. #Dancefloor 7. #Dubstep 8. #PJSpezial

a.1)

Geben Sie den binären Suchbaum an, der nach diesen Einfügevorgängen vorliegt. [4 Punkte]

a.2)

Erläutern Sie am Beispiel des zusätzlich einzufügenden Hashtags #Heavy, wie ein Element in den binären Suchbaum eingefügt wird. [3 Punkte]

a.3)

Stellen Sie einen Binärbaum dar, der sich ergibt, wenn zuerst der Hashtag #Heavy eingefügt und danach der Hashtag #Eminem gelöscht wird. [3 Punkte]

Teilaufgabe d)

Es soll eine Methode entstehen, die eine Liste aller Hashtag-Objekte zurückgibt, in deren Hashtag-Zeichenkette die übergebene Buchstabenfolge vorkommt. Die öffentliche Methode erhält diesen Methodenkopf:

public List<Hashtag> liefereHashtags(String pSubstring) d.1)

Entwickeln Sie einen algorithmischen Ansatz, mit dem die Methode ihre Aufgabe erfüllt. [5 Punkte]

d.2)

Implementieren Sie die Methode liefereHashtags sowie gegebenenfalls benötigte Hilfsmethoden. [8 Punkte]

Hinweis: Im Anhang finden Sie einen Auszug aus der Dokumentation der Klasse String.