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

Aufgabenstellung: Immobilienbewertung Firma Besserwohnen

Besserwohnen ist ein Unternehmen, das in einer ländlichen Region Wohnungen erwirbt, veräußert und vermietet. Es soll ausschließlich in Wohnungen investiert werden, bei denen mit einer Wertsteigerung zu rechnen ist.

Damit die Beschäftigten bei der Entscheidung über den Kauf neuer Wohnungen Unterstützung erhalten, hat eine Expertengruppe des Unternehmens auf Grundlage früherer Wohnungskäufe ein Einschätzungsverfahren auf Basis eines Binärbaums entwickelt. Es liefert anhand der folgenden drei nummerierten Kriterien für eine neue Wohnung entweder eine Kaufempfehlung oder keine.

Zimmeranzahl (Kriteriumnummer 0)

Quadratmeterpreis: Preis für je einen Quadratmeter in Euro (Kriteriumnummer 1)

Größe: Wohnungsgröße in Quadratmetern (in der Klausur mit qm abgekürzt) (Kriteriumnummer 2)

In Abbildung 1 ist der Binärbaum dargestellt, den die Firma Besserwohnen derzeit verwendet. Ein derartiger Baum heißt im Folgenden Einschätzungsbaum.

Man startet an der Wurzel und beantwortet für eine neue Wohnung die dort stehenden Fragen. Schon in jedem Knoten liegt eine Einschätzung vor, ob der Kauf empfohlen wird oder nicht (AKTUELLE KAUFEMPFEHLUNG). Enthält ein Knoten eine weitere Frage, ist die Einschätzung voraussichtlich besser, wenn man auch diese für die betrachtete Wohnung beantwortet und dann bei Ja in den linken, bei Nein in den rechten Teilbaum wechselt.

Die Einschätzung einer neuen Wohnung mithilfe des Baums endet erst, wenn ein Blatt erreicht ist oder der in einem Knoten zu vergleichende Kriterienwert wegen unvollständiger Angaben zur Wohnung fehlt.

Die Ermittlung der Einschätzungen soll durch ein Programm automatisch erfolgen. Abbildung 3 stellt einen Ausschnitt des Implementationsdiagramms des Einschätzungsprogramms der Firma Besserwohnen dar.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Einschaetzungsprogramm

Objekte der Klasse Einschaetzungsprogramm dienen der Einschätzung von neuen Wohnungen hinsichtlich der Frage, ob sie zur weiteren Vermarktung angekauft werden sollten.

Auszug aus der Dokumentation der Klasse Einschaetzungsprogramm

Einschaetzungsprogramm()

Ein Objekt der Klasse Einschaetzungsprogramm wird initialisiert.

boolean ermittleKaufempfehlung(Wohnung pWohnung)

Die Anfrage liefert true, falls eine Kaufempfehlung für die übergebene Wohnung pWohnung gegeben wird. Sonst liefert sie false.

public void macheEtwas(List<Boolean> pPfad, Frage pFrage, boolean pKaufempfehlungBeiJa)

Die Methode wird in Aufgabenteil d) untersucht.

Die Klasse Wohnung

Ein Objekt der Klasse Wohnung repräsentiert eine Wohnung und verwaltet ihre Eigenschaften.

Auszug aus der Dokumentation der Klasse Wohnung

Wohnung(Integer pZimmeranzahl, Integer pQuadratmeterpreis, Integer pGroesse)

Ein Objekt der Klasse Wohnung wird initialisiert. Die als Parameter übergebenen Werte werden übernommen. Für Werte, die für die zugehörige Wohnung nicht vorliegen, soll dabei null übergeben werden.

Integer gibWert(int pKriteriumnummer)

Die Anfrage liefert den eingetragenen Wert des Kriteriums mit der als Parameter übergebenen Nummer pKriteriumnummer. Hierbei steht die Nummer 0 für die Zimmeranzahl, die Nummer 1 für den Quadratmeterpreis und die Nummer 2 für die Größe. Bei allen anderen Werten von pKriteriumnummer wird null zurückgeliefert. Wurde bei Erstellung des Wohnung -Objekts für ein Kriterium der Wert null übergeben, so wird entsprechend null als Wert von diesem Kriterium zurückgegeben.

Die Klasse Inhalt

Ein Objekt der Klasse Inhalt repräsentiert den einem Knoten eines Einschätzungsbaums zugewiesenen Inhalt. Mit einem Objekt der Klasse Inhalt kann daher sowohl die Einschätzung bzgl. einer Kaufempfehlung gemäß der Position im Baum gespeichert werden als auch eine präzisierende Frage in Form eines Objekts der Klasse Frage verwaltet werden.

Auszug aus der Dokumentation der Klasse Inhalt

Inhalt(boolean pKaufempfehlung)

Ein Objekt der Klasse Inhalt wird initialisiert und speichert den als Parameter übergebenen Wert pKaufempfehlung. Es wird zu Beginn kein Objekt der Klasse Frage verwaltet.

boolean gibKaufempfehlung()

Die Anfrage liefert den gespeicherten Wert für eine Kaufempfehlung.

Frage gibFrage()

Falls ein Objekt der Klasse Frage von diesem Inhalt -Objekt verwaltet wird, so wird es zurückgegeben. Sonst wird null zurückgegeben.

void setzeFrage(Frage pFrage)

Das als Parameter übergebene Objekt wird gespeichert. Wird null übergeben, so verwaltet dieses Inhaltsobjekt nach Ausführung kein Objekt der Klasse Frage.

Die Klasse Frage

Ein Objekt der Klasse Frage repräsentiert eine Frage, bei der der Wert eines Kriteriums einer Wohnung mit einem Schwellenwert verglichen wird. Hierfür verwaltet ein Objekt der Klasse Frage die Nummer eines Kriteriums und den Schwellenwert.

Auszug aus der Dokumentation der Klasse Frage

Frage(int pKriteriumnummer, int pSchwellenwert)

Ein Objekt der Klasse Frage wird mit den als Parameter übergebenen Werten initialisiert.

String gibAntwort(Wohnung pWohnung)

Wenn bei der übergebenen Wohnung pWohnung kein Wert für das Kriterium mit der von der Frage verwalteten Kriteriumnummer eingetragen ist, sondern dort null eingetragen ist, dann ist kein Vergleich mit dem Schwellenwert möglich und die Methode liefert den Wert null. Sonst vergleicht die Methode den betreffenden Kriterienwert der Wohnung mit dem von der Frage verwalteten Schwellenwert und gibt die Zeichenkette (den String) "Ja" zurück, falls der betreffende Kriterienwert der Wohnung kleiner gleich dem Schwellenwert ist, und gibt andernfalls die Zeichenkette (den String) "Nein" zurück.

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.

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 BinaryTree<ContentType>

Mithilfe der generischen Klasse BinaryTree können beliebig viele Objekte vom Typ ContentType in einem Binärbaum verwaltet werden. Ein Objekt der Klasse stellt entweder einen leeren Baum dar oder verwaltet ein Inhaltsobjekt sowie einen linken und einen rechten Teilbaum, die ebenfalls Objekte der generischen Klasse BinaryTree sind.

Dokumentation der Klasse BinaryTree<ContentType>

BinaryTree()

Nach dem Aufruf des Konstruktors existiert ein leerer Binärbaum.

BinaryTree(ContentType pContent)

Wenn der Parameter pContent ungleich null ist, existiert nach dem Aufruf des Konstruktors der Binärbaum und hat pContent als Inhaltsobjekt und zwei leere Teilbäume. Falls der Parameter null ist, wird ein leerer Binärbaum erzeugt.

BinaryTree(ContentType pContent, BinaryTree<ContentType> pLeftTree, BinaryTree<ContentType> pRightTree)

Wenn der Parameter pContent ungleich null ist, wird ein Binärbaum mit pContent als Inhaltsobjekt und den beiden Teilbäume pLeftTree und pRightTree erzeugt. Sind pLeftTree oder pRightTree gleich null, wird der entsprechende Teilbaum als leerer Binärbaum eingefügt. Wenn der Parameter pContent gleich null ist, wird ein leerer Binärbaum erzeugt.

boolean isEmpty()

Diese Anfrage liefert den Wahrheitswert true, wenn der Binärbaum leer ist, sonst liefert sie den Wert false.

void setContent(ContentType pContent)

Wenn der Binärbaum leer ist, wird der Parameter pContent als Inhaltsobjekt sowie ein leerer linker und rechter Teilbaum eingefügt. Ist der Binärbaum nicht leer, wird das Inhaltsobjekt durch pContent ersetzt. Die Teilbäume werden nicht geändert. Wenn pContent null ist, bleibt der Binärbaum unverändert.

ContentType getContent()

Diese Anfrage liefert das Inhaltsobjekt des Binärbaums. Wenn der Binärbaum leer ist, wird null zurückgegeben.

void setLeftTree(BinaryTree<ContentType> pTree)

Wenn der Binärbaum leer ist, wird pTree nicht angehängt. Andernfalls erhält der Binärbaum den übergebenen Baum als linken Teilbaum. Falls der Parameter null ist, ändert sich nichts.

void setRightTree(BinaryTree<ContentType> pTree)

Wenn der Binärbaum leer ist, wird pTree nicht angehängt. Andernfalls erhält der Binärbaum den übergebenen Baum als rechten Teilbaum. Falls der Parameter null ist, ändert sich nichts.

BinaryTree<ContentType> getLeftTree()

Diese Anfrage liefert den linken Teilbaum des Binärbaumes. Der Binärbaum ändert sich nicht. Wenn der Binärbaum leer ist, wird null zurückgegeben.

BinaryTree<ContentType> getRightTree()

Diese Anfrage liefert den rechten Teilbaum des Binärbaumes. Der Binärbaum ändert sich nicht. Wenn der Binärbaum leer ist, wird null zurückgegeben.

Teilaufgabe a)

Zunächst gilt der Einschätzungsbaum aus Abbildung 1 als Grundlage. Abbildung 2 enthält die Werte zweier Wohnungen.

Wohnung 1

Wohnung 2

Zimmeranzahl

3

5

Quadratmeterpreis

25 €

30 €

Größe

70 qm

unbekannt

Abbildung 2: Die Daten zu zwei Wohnungen

Ermitteln Sie für jede der beiden Wohnungen aus Abbildung 2, ob sie eine Kaufempfehlung erhielte.

Geben Sie beispielhaft Zimmeranzahl, Quadratmeterpreis und Größe einer Wohnung an, für deren Einschätzung vier Fragen beantwortet werden müssten und die keine Kaufempfehlung erhielte.

Ermitteln Sie den Bereich, in dem die Größe einer Wohnung mit vier Zimmern und einem Quadratmeterpreis von 40 € liegen muss, um eine Kaufempfehlung zu erhalten.

Teilaufgabe c)

Die Klasse Einschaetzungsprogramm besitzt eine Methode ermittleKaufempfehlung mit dem folgenden Methodenkopf:

public boolean ermittleKaufempfehlung(Wohnung pWohnung)

Diese Methode ermittelt mit dem verwalteten Einschätzungsbaum für das übergebene Objekt der Klasse Wohnung, ob eine Kaufempfehlung gegeben wird oder nicht.

Entwickeln und erläutern Sie ein algorithmisches Verfahren, das mithilfe des verwalteten Einschätzungsbaums die Kaufempfehlung für eine Wohnung bestimmt.

Implementieren Sie die Methode ermittleKaufempfehlung und gegebenenfalls weitere Hilfsmethoden entsprechend Ihrem Verfahren.

Teilaufgabe d)

In der Klasse Einschaetzungsprogramm wurde folgende Methode macheEtwas implementiert, die weder dokumentiert noch kommentiert wurde:

1 public void macheEtwas(List<Boolean> pPfad, Frage pFrage,

2 boolean pKaufempfehlungBeiJa) {

3 BinaryTree<Inhalt> bt = einschaetzungsbaum;

4 pPfad.toFirst();

5 while (pPfad.hasAccess() && !bt.isEmpty()) {

6 if (pPfad.getContent() == true) {

7 bt = bt.getLeftTree();

8 } else {

9 bt = bt.getRightTree();

10 }

11 pPfad.next();

12 }

13

14 if (!bt.isEmpty() && bt.getLeftTree().isEmpty()

15 && bt.getRightTree().isEmpty()) {

16 bt.getContent().setzeFrage(pFrage);

17 bt.getLeftTree().setContent(

18 new Inhalt(pKaufempfehlungBeiJa));

19 bt.getRightTree().setContent(

20 new Inhalt(!pKaufempfehlungBeiJa));

21 }

22 }

Analysieren Sie den Quelltext und erläutern Sie, wie die Methode macheEtwas arbeitet.

Erläutern Sie im Sachkontext, was die Methode macheEtwas leistet.

Teilaufgabe e)

Jeder Knoten im Einschätzungsbaum (vgl. Abbildung 1) repräsentiert eine Menge von Wohnungen, die über gleiche Eigenschaften hinsichtlich der drei Kriterien Zimmeranzahl, Quadratmeterpreis und Größe verfügen.

Das zweite Blatt von links im Einschätzungsbaum in Abbildung 1 repräsentiert z. B. alle Wohnungen, die eine Zimmeranzahl von höchstens 2 haben und deren Größe größer als 15 qm ist. Der Quadratmeterpreis darf beliebig sein.

Ein Softwareentwickler macht daher den folgenden Vorschlag: Zu jedem Knoten im Einschätzungsbaum, der eine positive Kaufempfehlung enthält, soll ein Objekt einer neuen Klasse Profil erzeugt werden. In diesem Objekt wird für jedes Kriterium gespeichert, in welchem Intervall (vom zu überschreitenden Minimalwert bis zum zulässigen Maximalwert) der Wert des entsprechenden Kriteriums liegen muss, damit man im Baum an die Stelle des entsprechenden Knotens gekommen wäre.

Statt des Baums in Abbildung 1 kann nun eine Liste der Objekte vom Typ Profil gespeichert werden. Hierbei müssen nur Profile mit Kaufempfehlung gespeichert werden. Die Einschätzung einer Wohnung wird wie folgt ermittelt: Wenn in der Liste ein Profil-Objekt gefunden werden kann, zu dem die Wohnung passt, so wird eine Kaufempfehlung gegeben, andernfalls nicht.

Beurteilen Sie den obigen Vorschlag dahingehend, ob er zu denselben Einschätzungen führt wie der Einschätzungsbaum.