Informatik Q12: Lernbereich 2

1. Konzept: Grenzen der Liste

In Lernbereich 2 haben wir Listen implementiert. Sie sind dynamisch, haben aber eine Schwäche.

Gedankenexperiment

Stell dir vor, eine Datenbank speichert 1.000.000 Einträge in einer Liste.

• Szenario A (Liste): Du suchst einen Eintrag, der ganz am Ende steht. Wie viele Vergleiche macht der Computer?
  Antwort: 1.000.000 Vergleiche.
• Szenario B (Baum): Wir nutzen eine Baumstruktur, die sich bei jedem Schritt verzweigt (links kleiner, rechts größer). Bei jedem Vergleich schließen wir die Hälfte der verbleibenden Daten aus.

Die Auswirkung:
Um unter 1.000.000 Einträgen zu suchen, braucht der Baum (im Idealfall) nur ca. 20 Vergleiche. Das ist der Unterschied zwischen "sofort da" und "Wartezeit".

2. Die Architektur (Kompositum)

Wir verwenden das Entwurfsmuster Kompositum. Es hilft uns, die Rekursion sauber zu programmieren, indem wir "leere" Enden als eigene Objekte behandeln.

Aufgabe 1: Wer ist zuständig?

Ordne die folgenden Aufgaben den Klassen Knoten oder Abschluss zu.

Aufgabe 2: Polymorphie verstehen

Warum leiten wir beide Klassen von der abstrakten Klasse Baumelement ab?

3. PRIMM: Einfügen (Aufbau)

Bevor wir suchen können, müssen wir Daten einfügen. Hier verändert sich die Struktur des Baums.

Predict (Vorhersage)

Wir haben einen leeren Baum (nur ein Abschluss). Wir fügen "Maus" ein. Danach fügen wir "Elefant" ein.

Beschreibe, wie sich die Objekte verändern.

Modify & Make (Implementierung)

Implementiere die Methode einfuegen in der Klasse Knoten.
Achtung: Da wir die Struktur ändern, geben Methoden im Kompositum oft das (neue) Objekt zurück!

public BaumElement einfuegen(DatenElement d) {
    if (this.inhalt.istGleich(d)) {
        // Element schon da -> keine Änderung
        return this; 
    } 
    else if (this.inhalt.istGroesserAls(d)) {
        // Nach links absteigen und Ergebnis speichern
        this.leNext = this.leNext.einfuegen(d);
    } 
    else {
        // AUFGABE: Was passiert rechts?
        // ???
    }
    return this;
}
    

this.riNext = this.riNext.einfuegen(d);

Die Abschluss-Klasse

Was macht der Abschluss, wenn einfuegen aufgerufen wird?

public BaumElement einfuegen(DatenElement d) {
    // Aus Abschluss wird Knoten!
    return new Knoten(d);
}
            

4. PRIMM: Suchen

Der Baum ist aufgebaut. Jetzt wollen wir prüfen, ob ein Wort enthalten ist.

Predict (Analyse)

Analysiere folgenden Code der Klasse Knoten. Was passiert Schritt für Schritt bei der Suche nach "Zebra", wenn die Wurzel "Maus" ist?

public boolean suchen(DatenElement d) {
    if (this.inhalt.istGleich(d)) {
        return true;
    } 
    else if (this.inhalt.istGroesserAls(d)) {
        return leNext.suchen(d);
    } 
    else {
        return riNext.suchen(d);
    }
}
    

Investigate (Untersuchen)

Wir haben in Modul 1 über Effizienz gesprochen. Wo genau im Code passiert die "Magie", die den Baum so schnell macht?

5. Traversierung

Manchmal wollen wir nicht suchen, sondern alles ausgeben (z.B. Wörterbuch drucken).

Strategien

Ein Baum ist nicht linear. Wir müssen eine Reihenfolge festlegen. Gegeben ist ein Baum: Wurzel(B), Links(A), Rechts(C).

Aufgabe: Implementiere ausgeben() so, dass die Buchstaben alphabetisch (A, B, C) erscheinen.

public void ausgeben() {
    // 1. ???
    System.out.println(this.inhalt);
    // 2. ???
}
    

leNext.ausgeben();
System.out.println(this.inhalt);
riNext.ausgeben();
            

6. Projekt & Abschluss

Zum Abschluss eine Aufgabe für Profis. Wir wollen wissen, wie tief der Baum ist (wie lang der längste Ast ist).

Aufgabe: Die Methode tiefe()

Die Tiefe eines Knotens ist die länge des Pfades eines Knotens bis zur Wurzel. Passend dazu ist die Höhe eines Baums ist die Tiefe eines Knotens der am weitesten von der Wurzel entfernt ist (also die maximale Tiefe). Die Wurzel hat die Tiefe 0, ein leerer Baum hat die Tiefe -1.

Versuche, die Methode für die Klasse Knoten zu schreiben.

public int tiefe() {
    int tL = leNext.tiefe();
    int tR = riNext.tiefe();
    return 1 + Math.max(tL, tR);
}