Sortierter Import lässt den Suchbaum entarten
Eine Stadtbibliothek speichert 20 000 Titel in einem binären Suchbaum, Schlüssel ist die ISBN-13 als ganze Zahl. Die Titel werden nächtlich aus einer CSV-Datei neu aufgebaut; die Datei ist nach ISBN aufsteigend sortiert, weil sie aus dem Verbundkatalog exportiert wird. Nach dem Import dauert die Suche nach einer vorhandenen ISBN im Mittel 1,8 s; bei einem Testimport mit zufällig gemischter Datei sind es 0,01 s. Bei etwa 20 000 Einträgen tritt außerdem sporadisch ein StackOverflowError auf, wenn rekursiv gesucht wird. Ein Praktikant schlägt vor, die Rekursion durch eine Schleife zu ersetzen, dann sei das Problem gelöst. Die Bibliothekarin möchte dauerhaft schnelle Suchen und zusätzlich Bereichsabfragen unterstützen („alle Titel mit ISBN zwischen X und Y“). Ein anderer Vorschlag lautet, einfach eine Hashtabelle zu verwenden.
1. Erklären Sie den Laufzeitunterschied zwischen den beiden Importvarianten mit der Form des Baums und schätzen Sie die Zahl der Vergleichsschritte ab.
Read the worked answer
Ursache. Bei aufsteigend sortiertem Einfügen ist jeder neue Schlüssel größer als alle bisherigen. Er wird daher immer zum rechten Kind des zuletzt eingefügten Knotens. Der Baum hat keine Verzweigung mehr, sondern ist eine lineare Kette der Tiefe n−1. Die Suchzeit hängt von der Höhe h ab: im balancierten Fall O(log n), in der Kette O(n).
Abschätzung. Bei 20 000 Knoten ist die Kette im Mittel etwa 10 000 Vergleiche tief, im schlechtesten Fall 20 000. Ein balancierter Baum hat Höhe ≈ log₂(20 000) ≈ 14,3, also rund 15 Vergleiche. Das Verhältnis ist etwa Faktor 700 bis 1300 – konsistent mit 1,8 s zu 0,01 s (Faktor 180; der Unterschied ist kleiner, weil Speicherzugriffe und Datenbankzugriffe den Anteil glätten).
StackOverflow. Die rekursive Suche legt pro Ebene einen Stackframe an. Bei Tiefe 20 000 überschreitet der Aufrufstapel die übliche Größe (oft 512 kB bis 1 MB), daher der Fehler. Auch das ist eine direkte Folge der Entartung, nicht der Rekursion an sich.
Wichtige Konsequenz. Die gemessene Zeit ist kein Zufallsschwanken, sondern eine strukturelle Eigenschaft. Ein Test mit sortierten und eines mit gemischten Daten sind daher Pflichtfälle für jede Baumimplementierung.
2. Bewerten Sie den Vorschlag des Praktikanten (Iteration statt Rekursion) und den Vorschlag der Hashtabelle im Hinblick auf die Anforderungen der Bibliothekarin.
Read the worked answer
Iteration statt Rekursion. Der Vorschlag beseitigt nur das Symptom StackOverflow: Die iterative Suche läuft in einer Schleife und braucht keinen Aufrufstapel. Die Laufzeit bleibt aber O(n), weil die Kette bestehen bleibt – 1,8 s pro Suche werden nicht besser. Bei 20 000 Titeln und vielen Zugriffen ist das nicht akzeptabel. Der Vorschlag ist also richtig, aber unzureichend; er löst ein Problem zweiter Ordnung.
Hashtabelle. Im Mittel O(1) pro Suche, das wäre für Punktabfragen sehr gut. Nachteile: (1) Bereichsabfragen sind nicht effizient möglich, weil die Hashfunktion die Ordnung zerstört – man müsste alle Einträge durchlaufen (O(n)) oder zusätzlich einen Index pflegen. (2) Sortierte Ausgaben („alle Titel alphabetisch“) entfallen. (3) Der Aufwand für gutes Rehashing und Lastfaktor muss beherrscht werden.
Abwägung. Die Anforderung „Bereichsabfrage“ schließt eine reine Hashtabelle als alleinige Struktur aus. Ein balancierter Suchbaum (AVL oder Rot-Schwarz) bietet O(log n) für Suchen, Einfügen, Löschen und Bereichsabfragen und erfüllt beide Anforderungen. Wenn nur Punktabfragen nötig wären, wäre die Hashtabelle die einfachere Wahl – die Bereichsabfrage ist hier das entscheidende Kriterium.
3. Entwerfen Sie ein Verfahren, das aus der sortierten CSV-Datei direkt einen möglichst flachen Baum aufbaut, und begründen Sie dessen Komplexität.
Read the worked answer
Idee: Median als Wurzel. Man baut den Baum aus dem sortierten Array rekursiv nach dem Teile-und-Herrsche-Prinzip auf:
build(links, rechts):
wenn links > rechts: return null
mitte = (links + rechts) / 2
knoten = new Knoten(array[mitte])
knoten.links = build(links, mitte - 1)
knoten.rechts = build(mitte + 1, rechts)
return knoten
Warum balanciert? In jedem Schritt halbiert der Median das Intervall. Jeder Teilbaum enthält höchstens ⌈n/2⌉ Knoten, die Höhe ist damit ⌈log₂(n+1)⌉. Bei 20 000 Titeln ergibt das eine Höhe von 15 – die Suche braucht höchstens 15 Vergleiche.
Komplexität. Jeder Knoten wird genau einmal erzeugt, die Laufzeit ist O(n), weil kein Vergleich zum Einordnen nötig ist (die Sortierung wird vorausgesetzt). Der Rekursionsstapel ist nur O(log n) tief, ein StackOverflow ist ausgeschlossen. Der Speicherbedarf ist O(n).
Einordnung. Das Verfahren nutzt aus, dass die Daten bereits sortiert vorliegen – ein Sonderfall, der beim nächtlichen Neuaufbau immer gilt. Für laufende Einfügungen am Tag reicht das nicht; dort braucht man entweder eine Rebalancierung (AVL-Rotationen, O(log n) pro Einfügen) oder man nimmt in Kauf, dass der Baum zwischen zwei Importen leicht aus dem Gleichgewicht gerät. Wichtig ist, den Aufbau nicht mit dem üblichen Einfügen in einen leeren Baum zu verwechseln – genau das war der Fehler.