Wenn du nicht draufkommst, schau mal hier: stackoverflow
ubik
Ja, das ist kein Problem. Die Aufgabenstellung lautete, einen balancierten Baum mit mindestens 4 Knoten nach der zweitkleinsten Zahl zu durchsuchen.
Und ein balancierter Baum mit 4 Knoten hat immer einen linken Teilbaum von der Wurzel aus.
Tja, jetzt frag ich mich nur noch, wie man die k-kleinste Zahl findet. Gar nicht so einfach!
eulerscheZahl
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.
ubik
Warum ist das eigentlich so, dass bei balancierten Bäumen Laufzeit O(log n) gilt und bei nicht balancierten Bäumen Laufzeit O(n)?
eulerscheZahl
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).
ubik
Rekursiver Durchlauf im Baum - Zeitkomplexität
Hallo,
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
