Rückblick - Informatik

Das kann ich jetzt

Ich kann die Begriffe Wurzel, Knoten, Blatt, Teilbaum, Höhe und Tiefe an einem Baum zeigen. (Baumstrukturen)

Ich kann einen Binärbaum in Preorder, Inorder und Postorder durchlaufen. (Binärbaum)

Ich kann die Suchbaumeigenschaft prüfen und einen binären Suchbaum aufbauen. (Binärer Suchbaum)

Ich kann erklären, warum ein Suchbaum entarten kann und was das kostet. (Binärer Suchbaum)

Ich kann sagen, was ein AVL-Baum zusätzlich leistet. (AVL-Baum)

Gemischte Aufgaben

Aufgabe 1: Einen Baum lesen

Die Werte 50, 30, 70, 20, 40, 60, 80 werden in dieser Reihenfolge in einen zunächst leeren binären Suchbaum eingefügt.

a) Zeichne den entstehenden Baum.

b) Gib die drei Durchläufe an: Preorder, Inorder, Postorder.

c) Welche Höhe hat der Baum? Wie viele Blätter hat er?

d) Warum ist die Inorder-Ausgabe eines binären Suchbaums immer sortiert? Begründe mit der Suchbaumeigenschaft.

e) Wie viele Vergleiche braucht die Suche nach der 40? Nach der 45?

Tipp zu b)

Die Namen sagen, wann die Wurzel selbst ausgegeben wird:

Preorder: Wurzel, dann links, dann rechts.
Inorder: links, Wurzel, rechts.
Postorder: links, rechts, dann Wurzel.

Der linke Teilbaum kommt immer vor dem rechten.

Lösung. Erfrage das Passwort bei deiner Lehrkraft.

Aufgabe 2: Wenn der Baum entartet

Dieselben sieben Werte werden nun in aufsteigender Reihenfolge eingefügt: 20, 30, 40, 50, 60, 70, 80.

a) Zeichne den entstehenden Baum.

b) Welche Höhe hat er jetzt? Wie viele Vergleiche braucht die Suche nach der 80?

c) Welcher linearen Datenstruktur entspricht dieser Baum? Was ist von der Suchbaum-Idee übrig geblieben?

d) Ein Baum mit n Knoten hat im günstigsten Fall die Höhe log₂(n), im ungünstigsten n. Rechne beides für n = 1000 aus und vergleiche.

e) Was leistet ein AVL-Baum an dieser Stelle, und was kostet es?

f) Nenne eine Situation aus der Praxis, in der Daten typischerweise schon sortiert ankommen – und erkläre, warum das den Fall aus b) gefährlich alltäglich macht.

Lösung. Erfrage das Passwort bei deiner Lehrkraft.

Aufgabe 3: Rekursiv über Bäume

Beantworte jede Teilaufgabe zuerst als Satz in der Form „Ein leerer Baum … / Sonst …", bevor du Code schreibst.

a) Wie bestimmt man die Anzahl der Knoten eines Binärbaums?

b) Wie bestimmt man seine Höhe?

c) Wie bestimmt man die Anzahl der Blätter?

d) Wie prüft man, ob ein Wert enthalten ist – einmal für einen beliebigen Binärbaum und einmal für einen Suchbaum? Worin unterscheiden sich die beiden Verfahren im Aufwand?

e) Warum ist bei Bäumen die Rekursion der Schleife klar überlegen – anders als bei den Aufgaben aus dem Rekursionskapitel?

Tipp: Das Muster

Jede dieser Fragen hat dieselbe Form:

Ein leerer Baum: <trivialer Wert>
Sonst: <etwas aus der Wurzel> kombiniert mit
       <derselben Frage für links> und <derselben Frage für rechts>

Bei der Anzahl ist die Kombination ein Plus, bei der Höhe ein Maximum, beim Enthaltensein ein Oder.

Lösung. Erfrage das Passwort bei deiner Lehrkraft.

Selbsttest

1. In welcher Reihenfolge besucht der Inorder-Durchlauf?

{r1{Wurzel, links, rechts}}

{r1{!links, Wurzel, rechts}}

{r1{links, rechts, Wurzel}}

{r1{rechts, Wurzel, links}}

{h{Die Silbe in sagt, wo die Wurzel steht: in der Mitte.}} {H{Richtig.}}

2. Was gilt für die Inorder-Ausgabe eines binären Suchbaums?

{r2{Sie beginnt mit der Wurzel.}}

{r2{!Sie ist aufsteigend sortiert.}}

{r2{Sie gibt zuerst alle Blätter aus.}}

{r2{Sie hängt von der Einfügereihenfolge ab.}}

{h{Links steht nur Kleineres, rechts nur Größeres – auf jeder Ebene.}} {H{Richtig – damit ist der Suchbaum zugleich ein Sortierverfahren.}}

3. Sieben Werte werden aufsteigend sortiert in einen leeren Suchbaum eingefügt. Welche Höhe hat er?

{z{7}}

{h{Jeder neue Wert ist größer als alle bisherigen – wohin hängt er sich?}} {H{Richtig – der Baum entartet zur Liste.}}

4. Wie viele Vergleiche braucht die Suche in einem ausgeglichenen Baum mit 1000 Knoten ungefähr?

{r3{1000}}

{r3{500}}

{r3{!10}}

{r3{100}}

{h{Jeder Vergleich halbiert die Menge – zweierlogarithmus von 1000.}} {H{Richtig. Im entarteten Baum wären es 1000.}}

5. Was leistet ein AVL-Baum gegenüber einem gewöhnlichen Suchbaum?

{r4{Er speichert mehr Werte.}}

{r4{!Er hält sich selbst im Gleichgewicht, sodass die Höhe klein bleibt.}}

{r4{Er sortiert beim Ausgeben.}}

{r4{Er braucht weniger Speicher.}}

{h{Was war das Problem beim sortierten Einfügen?}} {H{Richtig – erkauft mit mehr Aufwand beim Einfügen und Löschen.}}

6. Wie lautet der Basisfall bei rekursiven Baumalgorithmen fast immer?

{r5{ein Blatt}}

{r5{!der leere Baum}}

{r5{die Wurzel}}

{r5{ein Knoten mit genau einem Kind}}

{h{Welcher Fall ist so trivial, dass es nichts mehr zu tun gibt?}} {H{Richtig – das Blatt wird dadurch mit erledigt, weil seine Kinder leer sind.}}

7. Warum ist die Suche in einem beliebigen Binärbaum teurer als in einem Suchbaum?

{r6{Weil Binärbäume größer sind.}}

{r6{!Weil man ohne Ordnung beide Teilbäume durchsuchen muss statt nur einen.}}

{r6{Weil die Rekursion langsamer ist.}}

{r6{Sie ist nicht teurer.}}

{h{Was erlaubt der Vergleich mit der Wurzel im Suchbaum?}} {H{Richtig – er schließt einen ganzen Teilbaum aus.}}