Hallo,
wie zeigt man das:
man jeden binären Suchbaum in jeden anderen (mit gleichen Einträgen) mit Hilfe von O(n) Rotationen überführt werden kann?
Als Tip ist gegeben: Nach jeder Rotation eines binären Suchbaumes entsteht wieder ein binärer Suchbaum. Man soll sich nun überlegen, wie man vorgehen könnte, falls der Baum, den man überführt eine verkettete Liste von rechten Söhnen ist.
Ich dachte mir, dass man dies vermutlich per Induktion zeigen soll.
Der Induktions-Anfang ist klar. Wenn man nur zwei Konten hat, dann braucht man eine Rotation und man hat alle möglichen Darstellungen des Baumes.
Der Induktionsschritt (n -> n+1) bereitet mir jedoch Probleme. Per IV kann man ja voraussetzen, dass man die n Elemente des Baumes in O(n) durch Rotation in jeden beliebigen Baum überführen kann. Mir ist dann aufgefallen, dass das eine weitere "neue" Element nicht stört, wenn man den Baum mit alten n Elementen rotiert und halt nur bei dem Knoten bleibt, wo man das n+1te Element angefügt hat.
Da man ja jetzt noch nicht mit diesem Element rotiert hat, hat man ja noch nicht alle Möglichen Darstellungen des Baumes dargestellt. Dies geht ja wenn man das n+1te Element mit den restlichen (schon rotierten) Elementen der jeweiligen Darstellungen rotiert.
Also z.B. um eine gewünschte Darstellung herbeizurufen hat man für die n Elemente (nach IV) O(n) gebraucht. Jetzt möchte ich es aber noch mein n+1tes angefügte Element an eine bestimmte Position des Baumes bringen. Da der Baum ja n weitere Knoten hat, kann man also auch max. n weitere Rotationen ausführen, bis n+1 an jeder einzelnen Position des neuen Baumes war. Also auch O(n).
Da O(n) + O(n) = O(n) geht dies in O(n).
q.e.d.
Aber stimmt das?
Vielen Dank. :)
