Lösung zu Aufgabe 6

In einen (leeren) binären Suchbaum sollen folgende Einträge eingefügt werden:

15, 46, 1, 28, 100, 99, 3 Gib jeweils eine Einfügereihenfolge an, bei der der binäre Suchbaum maximale (d.h. 7) bzw. minimale (d.h. 3) Höhe hat. Finde eine allgemeine Strategie für die minimale Höhe.

Maximale Höhe

Eine mögliche Einfügereihenfolge ist: 100, 99, 46, 28, 15, 3, 1. Dies ergibt folgenden Baum:

Minimale Höhe

Eine mögliche Einfügereihenfolge ist: 28, 3, 1, 15, 99, 46, 100. Dies ergibt folgenden Baum: Allgemeine Strategie:

1. Suche einen Wert, für den sich die Anzahl der kleineren Werte und die Anzahl der größeren Werte um höchstens 1 unterscheiden. Füge ihn ein.
2. Füge die Werte ein, die kleiner als der Wert von 1. sind (rekursiv nach demselben Schema).
3. Füge die Werte ein, die größer als der Wert von 1. sind (rekursiv nach demselben Schema).