Matematické Fórum

Ahoj všem,

řeším úlohu :

Do prázdného binárního vyhledávacího stromu bylo přidáno 1000 prvků. Předpokládejte, že do BVS jsou vkládána náhodná neopakující se čísla. V tomto stavu byly změřeny doby potřebné pro provedení následujících operací:

Přidání prvku - 8ms.
Odebrání prvku - 9ms.
Zjištění maxima ve stromu -10ms.
Vypsání celého stromu - 400ms.

Následně byly přidávány další prvky, až jejich počet dosáhl 1 000 000. Odhadněte dobu potřebnou pro provedení operací v BVS v tomto stavu
Přidání prvku - ?
Odebrání prvku - ?
Zjištění maxima ve stromu - ?
Vypsání celého stromu - ?

-------------------
Takže uvažuji, že průměrná složitost přidání, odebírání je O(n) =log(n). Podle mě i hledání maxima, jelikož jdu pouze po pravé větvi.
Se složitostí vypsání celého stromu to zřejmě bude O(n).

Jak tedy postupovat?
Přidání :

Napadá mě toto:
Spočtu dobu přidání 1000 prvků : T(1000) = log(1000)*8 = 24ms
Spočtu dobu přidání 1000 0000 prvků : T(1000 000) = log(1000 000)*8 = 48ms

Doba po přidání dalších 999 000 prvků na 1000 000 prvků je 48-24 =24ms?

Vypsání všech :
400ms = 1000*t ... t doba vypsani jednoho prvku
t= 0,4ms

Takže doba vypsání 1000 000 prvků je 400 000ms ? děkuji