Bäume

Wichtige Inhalte zum Thema "verzweigte Datenstrukturen, Bäume"

Im Zentralabitur NRW kommen nicht nur binäre Suchbäume vor, sondern ganz allgemein Baumstrukturen, zum Beispiel um die Ahnen oder Nachkommen von berühmten Menschen darzustellen oder um arithmetische Ausdrücke mit Hilfe von Parsebäumen zu veranschaulichen. Meistens werden aber tatsächlich binäre Suchbäume thematisiert.

Was ein binärer Suchbaum ist wird auf dieser Seite erläutert.

Die Meinung darüber, ob binäre Suchbäume zu den Abstrakten Datentypen gehören oder nicht vielmehr Datenstrukturen sind, gehen oft auseinander. Man kann den ADT Binärer Suchbaum tatsächlich allgemein definieren, und zwar durch die Operationen

• Init(): Erzeugt einen leeren Suchbaum.
• Insert(x): Das Element x wird hinzugefügt, und zwar in den linken Unterbaum, wenn es kleiner ist als die Wurzel, ansonsten in den rechten Unterbaum.
• Remove(x): Das Element x wird entfernt, falls es vorhanden ist.
• Member(x): Falls das Element x im Baum vorhanden ist, wird TRUE zurückgeliefert, ansonsten FALSE.
• Empty(): Falls der Binärbaum leer ist, wird TRUE zurückgeliefert, sonst FALSE.

Entscheidend ist hier die Beschreibung der Insert()-Operation, sie gibt quasi vor, wie der binäre Suchbaum aufzubauen ist.

Fürdie schriftliche Abiturprüfung ist die Implementation eines binären Suchbaums eigentlich eher unwichtig, vielmehr ist der Umgang mit der Klasse BinarySearchTree bzw. mit den vielen Methoden dieser Klasse wichtig. Allerdings sollten Sie trotzdem wissen, wie man eine rekursive Insert()-Methode und eine rekursive Show()-Methode implementiert, das wäre vor allem für die mündliche Prüfung wichtig, wo so etwas durchaus mal abgefragt werden kann. Und natürlich sollten Sie in der Lage sein, vorgelegte Java-Quelltexte mit Implementationen der BinarySearchTree-Methoden zu analysieren und zu erläutern.

Ein Implementationsdiagramm, in dem ein Objekt der Klasse BinarySearchTree verwendet wird

Hier sehen wir wieder mal ein Implementationsdiagramm aus einer Abituraufgabe von 2018. Es soll eine Eventverwaltung modelliert werden, und der Ticketmanager verwaltet die vielen Kunden in einem binären Suchbaum. Das Attribut kunden ist ein Objekt der Klasse BinarySearchTree.

Wichtig für einen binären Suchbaum ist hier das Interface ComparableContent. Wenn dieses Interface von einer Klasse wie Person eingebunden wird, dann muss (!) die Klasse Person die drei im Interface angegebenen Methoden auf jeden Fall implementieren. Und zwar genau so, wie es im Interface vorgegeben wurde, also mit dem gleichen Bezeichner isEqual(), isLess() bzw. isGreater() und mit den gleichen Parametern.

Bei einem binären Suchbaum, der nur aus int-Zahlen besteht, sind solche Vergleichsmethoden nicht notwendig, da man auf int-Zahlen (oder auch double-Zahlen) die Vergleichsoperatoren =, < und > anwenden kann. Wenn der Baum aber komplexere Inhalte verwaltet wie zum Beispiel Objekte der Klasse Person, dann kann man diese einfachen Vergleichsoperatoren =, < und > nicht mehr anwenden. Denn wann ist denn die Person A kleiner als Person B? Das muss doch genau definiert werden. Und dazu dienen dann die drei Vergleichs-Methoden, die entweder true oder false zurückliefern, jenachdem ob Person A gleich, kleiner bzw. größer ist als B.

Schauen wir uns nun mal typische Aufgaben an, die in dieser Abiturklausur gestellt wurden.

In der ersten Aufgabe bekamen die Schüler(innen) eine Liste von Kunden, die durch ihre Ausweisnummern identifiziert wurden, zum Beispiel P12. Die Kunden sollten dann in einen binären Suchbaum eingebaut werden, und der Suchbaum sollte graphisch dargestellt werden. Dann sollten die Schüler(innen) beschreiben, wie man einen bestimmten Kunden (den letzten) in den bestehenden Suchbaum einfügt bzw. wie die Einfügestelle gefunden wird.

In der zweiten Aufgabe sollten die Schüler(innen) das obige Implementationsdiagramm beschreiben und dann die Methode isLess() der Klasse Person in Java implementieren.

Die dritte Aufgabe war dann wieder das Analysieren einer vorgegebenen wasLiefereIch()-Methode.

Nun wurde es kompliziert. Die Schüler(innen) sollten die Ergebnisse der wasLiefereIch()-Methode in einer Liste speichern (also in einem Objekt der Klasse List), und dann die Elemente der Liste wieder in einen neuen leeren Baum einspeichern.

In der vierten Aufgabe sollten Hausverbote für bestimmte Kunden implementiert werden: "Implementieren und dokumentieren Sie durch Quelltextkommentare die Methode erteileHausverbot der Klasse Ticketmanagergemäß der Dokumentation im Anhang."

Muss man im Zentralabitur einen binären Suchbaum implementieren können?

Diese Frage kann eindeutig mit "nein" beantwortet werden. Die Abituraufgaben der drei letzten Jahre, also 2018, 2019 und 2020 enthalten immer nur Aufgaben, bei denen mit den Methoden der Klasse BinarySearchTree gearbeitet werden muss. Keine der Abituraufgaben enthielt die Aufforderung, eine insert(), show() oder gar delete()-Methode für die Klasse BinarySearchTree in Java zu implementieren.

Aber im mündlichen Abitur?

In einer mündlichen Prüfung kann es durchaus vorkommen, dass eine statische oder dynamische Implementation einer insert()- oder show()-Methode verlangt wird, am besten natürlich rekursiv. Solche Implementationen finden sich zum Beispiel auf diesen Seiten: insert()-Methode, show()-Methode.

Was ist eigentlich mit diesen Implementationsdiagrammen, die man immer sieht?

Meistens sehen die Implementationsdiagramme furchtbar kompliziert aus, aber wenn man sie sich näher ansieht, sind sie oft recht einfach zu verstehen. Typische Aufgaben dazu sind die Analyse und Beschreibung eines solchen Implementationsdiagramms, manchmal auch die Erweiterung eines vorhandenen Diagramms. Noch nie verlangt wurde das Zeichnen eines komplett neuen Implementationsdiagramms.

Für die Klausur sollten Sie sich auf jeden Fall möglichst viele Implementationsdiagramme aus älteren Abiturklausuren ansehen und versuchen, diese zu verstehen.