die Aufgabe lautete, man solle den zweitkleinsten Wert im Baum finden mit Laufzeit O(log(n)).
Mein Algorithmus lautet:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
algorithm SecondSmallestNumber (B)
{ Eingabe: B Wurzel des Baumes }
if B^.lTree != nil then
if B^.lTree^.lTree != nil then
return SecondSmallestNumber(B^.lTree);
else
return B^.key;
end if
Der Algorithmus sieht gut aus.
Die Laufzeit kriegst du über die Tiefe des Baums, die ja logarithmisch von der Anzahl der Werte abhängt (sofern der Baum balanciert ist).
Ein nicht balancierter Baum ist im Extremfall einfach eine Liste. Und da brauchst du lineare Zeit zum Durchgehen.
Ach ja: wenn der Wurzelknoten des Baums keinen linken, sondern nur einen rechten Kindknoten hat, findest du die zweitkleinste Zahl nicht.
