Aufgabe 15 · ohne C++Vier Bäume.
15 / 17
Vier Bäume.
Vier TÜV-Berichte.
Deine Mission
Finde bei jedem Baum den ersten konkreten Regelverstoß. Nicht umbauen – nur sauber diagnostizieren.
Prüfungsauftrag: „Begründen Sie jeweils warum.“
Dein erster Zug · 20 Sekunden
Was prüfst du außer der Schlüsselzahl?
Die 3 Prüfbrillen
Erst wenn alle drei passen, kommt die Bonusfrage: Kann dieser Baum durch reguläres 2-3-4-Einfügen überhaupt entstanden sein?
Werkbank
Klicke pro Baum den TÜV-Befund
Baum 1Wo fehlt etwas?
Baum 2Folge jedem Weg zum Blatt.
Baum 3Prüfe die Wertebereiche.
Baum 4 · Boss-LevelFormal okay – aber baubar?
Hinweis 1 · Blickrichtung
Prüfe mechanisch: Schlüssel zählen → Kinder zählen → Tiefenwege zählen → Buchstabenintervalle prüfen.
Markiere bei jedem inneren Knoten gedanklich die Lücken: vor dem ersten Schlüssel, zwischen je zwei Schlüsseln und nach dem letzten. Jede Lücke braucht genau ein Kind.
Hinweis 2 · Mechanik
Ein Beispiel, noch ohne die vier Befunde.
[c | h] teilt in drei Bereiche: <c, c…h, >h. Ein innerer Knoten mit zwei Schlüsseln braucht deshalb drei Kinder. Für die Balance zählst du jede Kante von der Wurzel bis zu jedem Blatt.Vollständiger Musterweg
Prüfe erst alle vier Bäume – oder decke die Lösung bewusst auf.
- Baum 1 – Kinderzahl: Der innere Knoten
c hhat zwei Schlüssel und müsste daher drei Kinder besitzen. Zwischencundhfehlt ein Kindknoten; vorhanden sind nuraundk. - Baum 2 – Blattebene: Nicht alle Blätter liegen auf demselben Niveau. Links erreicht man
a/e/hfrüher als rechtso/q/x/z(in der Musterlösung: rechts Höhe 4, links Höhe 3). Der Baum ist nicht balanciert/vollständig im Sinn des 2-3-4-Baums. - Baum 3 – Suchordnung: Beim Knoten
d e hmüsste das zweite Kind Werte zwischendundeenthalten. Dort stehtc; aberc < d. Also ist es kein Suchbaum. - Baum 4 – Entstehung: Kinderzahl, Blattebene und Suchordnung stimmen formal. Trotzdem kann kein regulärer Einfügeverlauf genau diese Form erzeugen: Damit
d g jentsteht, muss ein Schlüssel aus einem vollen Kind hochgeschoben worden sein. Der Split erzeugt dabei zwei Ein-Schlüssel-Knoten. Einer kann den nächsten Wert aufnehmen, mindestens einer müsste aber noch nur einen Schlüssel besitzen. Die vier gezeigten Kinder mit jeweils zwei bzw. drei Schlüsseln können daher nicht zusammen mit dem unveränderten Knotend g jentstanden sein.
Merksatz für die Klausur: „Schlüsselzahl allein reicht nicht: Ich prüfe Kinderzahl, gleiche Blattebene, Suchbereiche – und bei formal gültigen Sonderfällen die Erreichbarkeit durch Splits.“
Wie sitzt Aufgabe 15?
Kannst du alle vier Verstöße ohne Aufdecken benennen?