[ALGORITMI] Costo ricerca in un ABR

[HoldenCaulfield1987]

Spero di essere nella sezione più appropriata.

Sto studiando dal punto di vista algoritmico gli alberi binari di ricerca.
So che ad esempio per una ricerca il tempo di esecuzione è O(h), dove h è l'altezza dell'albero.
La cosa che onestamente mi fa impazzire è il COME viene calcolato quel tempo di esecuzione.
M spiego meglio:
quel tempo di esecuzione indica il numero di nodi visitati oppure il numero di chiamate ricorsive effettuate a partire dal figlio (sx o dx che sia) della radice?
A me verrebbe più facile pensare al numero di nodi visitati, però cosi non considero la visita al nodo di partenza, ovvero al nodo radice.
E' anche vero però che asintoticamente dire h (quindi tutti i nodi interni e la foglia) + 1 (la radice) è uguale a dire solo h.

Come forse avrete capito ho un po' di confusione a riguardo.
Mi date una mano?

Grazie

[SerMagnus]

il costo della ricerca binaria è log(2) n.

il calcolo viene effettuato tenendo conto delle sole istruzioni dominanti dell'algoritmo

[HoldenCaulfield1987]

Si, ma se il costo di una ricerca/cancellazione/inserimento è O(h), in h è considerata la visita del nodo radice (ma nascosta dalla notazione asintotica), oppure non viene considerata?

[SerMagnus]

beh siccome la ricerca binaria dimezza ad ogni passo la dimensione della sequenza da valutare, ti troverai comunque che ad ogni passo valuterà, log(2) n, dove con n è inidicata la grandezza della sequenza corrente, o in altri termini la profondità dell'albero binario a partire dal nodo corrente

[HoldenCaulfield1987]

Quindi se ho capito bene tu calcoli:
un numero c di operazioni di costo costante per la visita del nodo radice + il costo delle visite ricorsive ai figli.

[SerMagnus]

ora nn ricordo di preciso, però in realtà durante il cacolo della complessità il numero di chiamate ricorsive non rientra nel cacolo, salvo se questa non fa parte di una delle istruzioni dominanti.

in realtà per la ricerca binaria devi considerare il numero di passi per discendere l'albero, a partire della seguenza in ingresso, ecco come esce fuori il valore di log(2) n

al generico passo k, ti trovi n/2^(k-1)