Suchbäume mit denselben Schlüsseln können unterschiedlich hoch sein.
Es kommt darauf an, in welcher Reihenfolge eingefügt wird.
Schlüssel:
24, 28, 50,
57, 66, 80
Füge diese Schlüssel in einen neuen (leeren) Suchbaum ein. Wähle dabei verschiedene
Reihenfolgen. Bei welchen Reihenfolgen bekommst du einen besonders hohen Baum?
Was weiß man über die Höhe, wenn man die Anzahl der Knoten kennt?
Richtig oder falsch?
Besonders die letzten beiden Fragen verdeutlichen, dass die Höhe eines binären Suchbaumes bei gleicher Knotenzahl enorm variieren kann.
Bearbeite mehrere Aufgaben!
Rotiert wird um einen Knoten des Suchbaumes, den du
per Klick auswählen kannst. Du kannst nach links oder nach rechts rotieren.
Verringere die Höhe des Baumes durch Rotieren.
(Die kleinen blauen Indizes brauchst du noch nicht zu beachten.)
Durch Links- und Rechtsrotationen kann man die Höhe eines binären Suchbaumes ändern.
wichtig
Sind alle Schlüssel im binären Suchbaum verschieden, so entsteht nach einer Rotation wieder ein binärer Suchbaum. Für jeden Knoten sind also auch nach der Rotation die Schlüssel des linken Teilbaumes kleiner und die des rechten Teilbaumes größer als der eigene Schlüssel.
aber
Kommt ein Schlüssel mehrfach vor, werden Linksrotationen problematisch: Sie können einen gleichen Schlüssel vom rechten in den linken Teilbaum `drehen', wo er aber eigentlich nicht liegen darf.
Vereinbarung
Zur Vereinfachung schließen wir deshalb ab sofort mehrfache Schlüssel aus.
