Aufbau und Funktionsweise
Schlag im Telefonbuch „Neumann" nach. Niemand fängt bei A an und blättert weiter – man schlägt in der Mitte auf, sieht „K", weiß damit, dass Neumann rechts liegen muss, und schlägt in der rechten Hälfte wieder mittig auf. Nach ein paar Griffen ist man da.
Das ist die binäre Suche aus 3.2, und sie setzt voraus, dass die Einträge sortiert daliegen. Bei einem Buch ist das so. Bei Daten, die laufend dazukommen und wieder verschwinden, wäre es teuer: Jeder neue Kontakt müsste an die richtige Stelle einsortiert werden, und alle dahinter müssten aufrücken.
Der binäre Suchbaum löst das. Er hält die Ordnung nicht in der Reihenfolge, sondern in der Form.
Ein binärer Suchbaum ist ein Binärbaum, in dem für jeden Knoten gilt:
- Alle Inhalte im linken Teilbaum sind kleiner als der Inhalt des Knotens.
- Alle Inhalte im rechten Teilbaum sind größer.
Diese Bedingung heißt Suchbaumeigenschaft. Sie gilt nicht nur an der Wurzel, sondern an jedem einzelnen Knoten.
Hier sind die Kontakte anhand der Benutzernamen einsortiert, verglichen wird alphabetisch:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Steht in einem Knoten der Benutzername fred, dann gehört alf in seinen linken Teilbaum und paul in seinen rechten.
Der Gewinn ist derselbe wie beim Telefonbuch: Jeder Vergleich halbiert die Menge der noch in Frage kommenden Einträge. Bei 1000 Kontakten reichen rund 10 Vergleiche statt 1000.
Der Preis dafür steht weiter unten – der Baum muss einigermaßen gleichmäßig gewachsen sein, sonst hilft die Ordnung nichts.
Kontakte suchen
Die Methode Contact search(Contact pContent) soll überprüfen, ob ein Kontakt mit einem bestimmten Benutzernamen im binären Suchbaum enthalten ist. Falls dies der Fall ist, dann liefert search das Kontakt-Objekt zurück, ansonsten wird null zurückgegeben.
- Such im Objektdiagramm oben Schritt für Schritt, ob der Kontakt
pContententhalten ist. Sag vor jedem Schritt voraus, ob es nach links oder nach rechts weitergeht. - Löse danach das Code-Puzzle unten zur Methode
searchund verfolge, welchen Weg die Suche durch den Baum nimmt.
Teillösung des Code-Puzzles
Kontakte einfügen
Die Methode void insert(Contact pContent) soll einen neuen Kontakt (pContent) in den binären Suchbaum einfügen. Das Vergleichskriterium soll hierbei der Benutzername (username) sein.
- Füge
pContentim Objektdiagramm oben Schritt für Schritt in den Suchbaum ein. - Entwirf zur Methode
insertder KlasseBinarySearchTreeeinen Algorithmus im Pseudocode. - Überprüfe deinen Algorithmus am Objektdiagramm: Führt er bei jedem Kontakt an dieselbe Stelle?
- Bereite dich darauf vor, deinen Algorithmus am Objektdiagramm zu erläutern.
Hilfe
Orientiere dich an der Lösung zur Methode search:
Den Baum selbst wachsen lassen
Hier kannst du beliebig viele Werte einfügen und suchen. Bei der Suche wird der Weg durch den Baum eingefärbt.
a) Suche die 20 und dann die 55. Wie viele Vergleiche braucht der Baum jeweils? Vergleiche mit der Zahl der Knoten.
b) Leere den Baum und füge die Werte 10, 20, 30, 40, 50 in dieser Reihenfolge ein. Beschreibe die Form, die entsteht, und lies die Höhe ab.
c) Leere ihn erneut und finde eine Reihenfolge derselben fünf Werte, bei der die Höhe so klein wie möglich wird. Die Anzeige „minimal möglich“ verrät dir das Ziel.
d) Erkläre daran, warum die Suche im Suchbaum zwar meistens schnell ist, aber keine Garantie dafür gibt.
Auflösung
a) Die 20 wird nach 3 Vergleichen gefunden (50 → 30 → 20), die 55 nach 3 Vergleichen nicht gefunden (50 → 70 → 60, und dort ist links ein leerer Knoten). Der Baum hat 7 Knoten – es werden also weniger als halb so viele Vergleiche gebraucht, wie es Knoten gibt.
Bemerkenswert ist der zweite Fall: Auch die erfolglose Suche ist schnell. Sie muss nicht alle Knoten prüfen, weil nach jedem Vergleich eine ganze Hälfte wegfällt.
b) Es entsteht eine Kette, die nur nach rechts wächst – jeder Wert ist größer als alle bisherigen und landet im rechten Teilbaum. Die Höhe ist 5, also so groß wie die Zahl der Knoten.
c) Zum Beispiel 30, 20, 40, 10, 50: Der mittlere Wert kommt zuerst an die Wurzel, danach jeweils die Mitte der verbliebenen Hälften. Die Höhe ist dann 3 – mehr geht bei fünf Knoten nicht, denn auf drei Ebenen passen höchstens 1 + 2 + 4 = 7 Knoten.
Das ist nicht die einzige Lösung. Auch 20, 10, 40, 30, 50 ergibt Höhe 3. Entscheidend ist nicht ein bestimmter Wert an der Wurzel, sondern dass die Werte nicht der Reihe nach kommen.
d) Die Suche ist schnell, solange der Baum gleichmäßig gewachsen ist. Wie er wächst, hängt aber allein von der Reihenfolge der Einfügungen ab – und die hat man meistens nicht in der Hand. Im günstigsten Fall halbiert jeder Vergleich die Menge (Höhe ≈ log n), im ungünstigsten entartet der Baum zur Kette (Höhe = n), und die Suche ist genauso langsam wie in einer Liste.
Eine Garantie gibt erst ein Baum, der sich selbst ausbalanciert – der AVL-Baum.