Rekursiver Durchlauf im Baum - Zeitkomplexität

07.05.2015, 09:12

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

Und die Kostenfunktion:

code:
1: 2: 3: 4: 5:	1 + T(n), falls linkerTeilbaum^.linkerTeilbaum ungleich nil T(n) = 1, sonst

Wie kann ich daraus die Laufzeit berechnen, sodass O(log(n)) rauskommt?

08.05.2015, 15:44

Auf diesen Beitrag antworten »

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).

09.05.2015, 09:31

Auf diesen Beitrag antworten »

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)?

09.05.2015, 10:09

Auf diesen Beitrag antworten »

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.

09.05.2015, 10:26

Auf diesen Beitrag antworten »

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! verwirrt

09.05.2015, 10:38

Auf diesen Beitrag antworten »

eulerscheZahl

Wenn du nicht draufkommst, schau mal hier: stackoverflow

Neue Frage »

Antworten »

Rekursiver Durchlauf im Baum - Zeitkomplexität

Verwandte Themen