Pages: 1 [2]   Go Down
Print
Author Topic: Dubbi quesiti compito: complessità di Successor(T,x) e vari  (Read 3121 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Jad1
Apprendista Forumista
**
Offline Offline

Posts: 120



« Reply #15 on: 09-12-2011, 17:47:08 »

Salve a tutti, nell'esercitarmi per l'esame di giovedi mi sono imbattuto nella seguente domanda:

"Sia T un albero binario di ricerca con n nodi e sia Successor(T,x) la procedura che ricerca il nodo in T il cui valore, nell'ordinamento lineare di tutti i valori di T, è il successore di x. Allora la complessità di Successor(T,x) è:
  a) O(logn)
  b) O(n)
  c) O(nlogn)
  d) Nessuna delle precedenti
"

La procedura Successor ha complessità O(h) dove h è l'altezza dell'albero binario, risposta che non compare tra quelle indicate. Però (ditemi se il ragionamento è errato), in ogni caso l'altezza massima di un albero non può essere superiore ad n (nel caso in cui sia completamente sbilanciato), per cui anche O(n) è un limite (seppur non stretto) per la procedura in quanto appunto T(n) = O(h)<=O(n). E' corretta quindi la risposta b?


scusate ragazzi ma a mio parere proprio perchè La procedura Successor ha complessità O(h) dove h è l'altezza dell'albero binario allora la risposta è la A..poichè un albero binario ha altezza h=logn...correggetemi se baglio..
Logged
InTheZone
Matricola
*
Offline Offline

Posts: 40



« Reply #16 on: 12-12-2011, 20:09:27 »

infatti non sbagli, il problema di un albero "lineare"(ovvero tutto sbilanciato a SX o DX) non si pone neanche, in quanto per definizione di BST a destra del nodo in questione vi sono tutti i nodi maggiori di esso.

Se ad esempio cerchiamo il successore della radice in un albero tutto sbilanciato a DX facciamo solo un passo!

Quindi la risposta giusta è O(h) dove h=log n.
 ciao
Logged
Pages: 1 [2]   Go Up
Print
Jump to: