Die Einführung und der Schlussteil werden gemeinsam erstellt. Die einzelnen Kapitel sind Individualarbeiten. Timur, Teil 1 und 3; Björn, Teil 2 und 4.
Das Leitprogramm richtet sich an Fachhochschul-Studenten und Studentinnen im 2. Semester des Informatik- oder Elektrotechnikstudiums. Im Besonderen ist dieses Leitprogramm für den Einsatz im Modul «Programmieren II» der Hochschule für Technik und Architektur Luzern (HTA) ausgerichtet.
Dieses Leitprogramm erläutert die wichtigsten Begriffe, Definitionen und Eigenschaften von Bäumen in der Informatik. Grundverstäntnisse für die Anwendung und Vorzüge von Suchbäumen als Datenstrukturen werden geschaffen. Die vier grundlegenden Operationen Traversierung, Einfügen, Löschen und Suchen werden erklärt und in Übungen programmiert. Im weiteren wird die Notwendigkeit für die Balacierung aufgezeigt und anhand der AVL-Bäume eine konkrete Methode geschildert.
Bäume sind ein wichtiges Konzept der Informatik und tretten in den verschiedensten Bereichen auf. Im besonderen sind Bäume eine wichtige Datenstruktur für die effiziente Speicherung von Daten und deren schnelle Auffindung.
Als Additum werden schwierigere Aufgaben z.B. das Löschen von Knoten und das implementieren von AVL-Bäume behandelt. Diese werden in den einzelnen Kapitel wiedergegeben und mit einem Stern markiert.
@book{goodrich,
Address = {Hoboken},
Author = {Michael T. Goodrich and Roberto Tamassia},
Edition = {3.},
Isbn = {0-471-46983-1},
Publisher = {John Wiley & Sons, Inc.},
Title = {Data Structures and Algorithms in JAVA},
Year = {2004}}
@book{widmayer,
Address = {Heidelberg, Berlin},
Author = {Thomas Ottmann and Peter Widmayer},
Edition = {4.},
Publisher = {Spektrum, Akad. Verl.},
Title = {Algorithmen und Datenstrukturen},
Year = {2002}}
Die Einleitung zeigt Bäume als Strukturierungsmittel und erläutert diese mit Beispielen und Verwendungsmöglichkeiten.
~ 15 min.
Die ersten Begriffe werden umgangssprachlich eingeführt: Baum, Blätter, Knoten, Wurzel, Vater, Kind, Geschwister, Vorfahren, Nachkommen, Höhe, Tiefe und Grad. Im weiteren geordnete und ungeordnete Bäume.
~ 30 min.
Um sich mit Algorithmen und Anwendungen im Zusammenhang mit Bäumen zu befassen, ist es erforderlich, dass der Student die grundlegenden Begriffe und Definitionen im Gebiet der Bäume kennt.
Der Binäre Suchbaum wird implementiert und traversiert.
~ 60 min
Um Binärbäume korrekt in einem Programm als Datenstruktur anzuwenden, ist es erforderlich, dass der Student den Aufbau und die Implementierung eines Binärbaumes und dessen Methoden kennt.
Der Student lernt die Theorie zum Einfügen und Suchen eines Elements kennen und kann diese dann gleich in die Praxis umsetzen. Das etwas schwierigere Löschen wird nur erläutert.
~ 120 min
Die wichtigsten Operationen Suchen, Einfügen und Löschen sind für den Einsatz von Suchbäumen als Datenstruktur unerlässlich. Für eine bestmögliche Anwendung der Bäume ist die Kenntnis über die Implementierung dieser Operationen nötig.
Was heisst balanciert? Was sind die Vorteile? Nachteile? Verstehen des Konzeptes von balancierten Bäumen anhand von AVL-Bäumen.
~ 90 min
Für die effiziente Anwendung von Binärbäumen als Datenstruktur ist ein balacierungs Kriterium notwendig, damit die Suchbäume ihre leistungsfähige Struktur langzeitig beibehalten.