Zum Hauptinhalt springen

Woche 13: Löschen in Bäumen & Hashing

letztes Übungsblatt

Beachten Sie, dass diese Woche das letzte Übungsblatt bearbeitet wird. Denken Sie daran, dass Sie sowohl für Zulassungsblock II, als auch insgesamt in Block I und II eine Mindestpunktzahl für die Klausurzulassung erreichen müssen.

Nach dieser Woche können Sie …

  • erklären, welche Vor- und Nachteile Hashsets gegenüber anderen Datenstrukturen haben

Wir beenden das Thema der Suchbäume, indem wir uns anschauen, wie man Elemente aus einem Baum löschen kann, ohne dass die Struktur des Baums kaputtgeht. Anschließend lernen wir eine Datenstruktur kennen, mit der es noch schneller möglich ist, Daten zu finden. Das ist z. B. dann relevant, wenn Sie eine große Produktdatenkbank haben und sehr oft Produkte anhand der Produktnummer finden wollen. Schließlich vergleichen wir alle Datenstrukturen, die wir kennengelernt haben, und schauen uns an, für welche Probleme welche Datenstruktur am besten passt.

Literatur

Falls Sie die Themen dieser Woche nochmal in der Literatur nachlesen wollen, können Sie sich das Kapitel Symbol Tables, insbesondere den Abschnitt Hash tables, in Introduction to Programming in Java ansehen.

Vorlesung​

Löschen aus Bäumen & generische Bäume​

CodeFolienAufzeichnung
Freiwillige Zusatzaufgaben
  • Schreiben Sie count() so um, dass die Anzahl der Baum-Elemente nicht berechnet wird, sondern eine der Wert einer privaten Instanzvariablen size zurückgegeben wird. size muss beim Einfügen und Löschen von Elementen korrekt erhöht/verringert werden.
  • Schreiben Sie einen StudiSearchTree (ohne Generics), in dem Studis nach Matrikelnummer sortiert sind. Schreiben Sie eine Methode, die zählt, wie viele Studis eine Matrikelnummer kleiner 300.000 haben, und eine weitere Methode, die zählt, wie viele Studis einen Namen haben, der mit „A“ anfängt. Bei welcher der beiden Methoden können Sie die Struktur (Sortierung) des Suchbaums ausnutzen?
  • zum Knobeln: Bearbeiten Sie die Zusatzaufgabe, die Sie in der Vorgabe für die Übungsstunden diese Woche finden.
  • zum Knobeln: Überlegen Sie sich ein iteratives Verfahren, um eine bestimmte Zahl aus einem binären Suchbaum zu löschen. (Achtung, es wird unübersichtlich! Machen Sie sich Skizzen.)

Hashing​

CodeFolienAufzeichnung
Freiwillige Zusatzaufgaben
  • Erinneren Sie sich an die Lotto-Übungsaufgabe? Dort haben Sie wahrscheinlich ein Array verwendet. Schreiben Sie den Code um, sodass stattdessen ein Hashset (für Integer) verwendet wird. Als Hashwert können Sie den Integer-Wert selbst nehmen.
  • zum Knobeln: Schreiben Sie eine Klasse HashMap, die ein Studi-Objekt unter einem selbst bestimmten int-Schlüssel (der gehasht wird) ablegen kann (void put(int key, Studi value)) und ein Objekt anhand des Schlüssels zurückgeben kann (Studi get(int key)). Bonus: Schreiben Sie eine generische HashMap<K,V>.
Berühmte Persönlichkeiten der Informatik

Dennis Ritchie und Ken Thompson haben das Betriebssystem Unix entwickelt, auf dessen Technologie viele heute genutzte Systeme wie macOS und das freie, von Linus Torvalds initiierte Linux (und damit auch Android) basieren. Ritchie und Thompson erhielten für ihre Arbeit 1983 den Turing Award. Thompson hat die Programmiersprache B entwickelt, die später von Ritchie zu C weiterentwickelt worden ist, um darin Unix neu zu schreiben.

C lernen Sie noch in der Veranstaltung C-Programmierung für Algorithmen und Datenstrukturen kennen. Da die Java-Syntax an C angelehnt ist, wird Ihnen vieles bekannt vorkommen.

Video über Thompson und Ritchie

#include <stdio.h>
 
int summe(int n) {
    int ergebnis = 0;
    for(int i = 1; i <= n; i++) {
        ergebnis += i;
    }
    return ergebnis;
}
 
int main(void) {
    printf("%d\n", summe(6));
}

Foto von Ritchie und Thompson