1. März 2009 – Johannes Pieper

Unterrichtsbeispiele für binäre Suchbäume (Pieper)

Im Lehrplan für den Informatikunterricht der Jahrgangsstufe 12 wird als Sachgegenstand der binäre Suchbaum angegeben. Die Schülerinnen und Schüler sollen mit binären Suchbäumen arbeiten können. Damit stellt sich die Aufgabe, einen Kontext zur Einbettung und Motivation zu finden. Eine Möglichkeit besteht darin, die Problemstellung als Auftrag an eine Firma zu inszenieren. Diese Firma bekommt den Auftrag, eine Datenstruktur zu entwerfen, um die stetig wachsende Zahl an Kunden aufzunehmen und gleichzeitig sicherzustellen, dass jeder Kunde durch Angabe seines Namens einfach gefunden werden kann.

Beispieldaten

Nun gilt es Musterkunden zu finden, mit denen die Schülerinnen und Schüler den entsprechenden Baum beispielhaft erstellen können, um ein entsprechendes Design zu finden. Natürlich ist es möglich, sich verschiedene Namen auszudenken, die einen möglichst gut balancierten Baum ergeben. Eine Alternative dazu bietet sich aber mit den Bundespräsidenten der Bundesrepublik Deutschland an. Erstellt man aus den Namen in der zeitlichen Reihenfolge einen Baum, so erhält man einen balancierten Binärbaum.

Dabei kann entweder die Liste der Präsidenten mit ihrer Amtszeit den Schülerinnen und Schülern an die Hand geben werden oder man hängt die Namen in entsprechender Reihenfolge an die Tafel. Erstaunlich war bei der zuletzt genannten Vorgehensweise, dass ein Schüler schon nach dem zweiten Namen die Fortsetzung der Reihe von sich aus nannte.

Rechtslastiger Suchbaum

Dass Vorlagen nicht immer so gut passen, zeigt sich an einem sehr verwandten Beispiel. Nimmt man die Liste der Bundeskanzler in der Reihenfolge ihrer Amtszeiten, so erhält man einen eher rechtslastigen Suchbaum. Dieses beginnt schon mit Adenauer, der auch in alphabetischer Ordnung an erster Stelle steht. Daher bleibt der komplette linke Teilbaum leer.

Es entsteht dabei aber noch keine Liste, die das Extrem eines nicht balancierten Baumes darstellt. Dieses Beispiel kann aber gut als Motivation für entsprechende Optimierungsmaßnahmen genutzt werden.