Siano dati due alberi binari di ricerca: B1 con n1nodi ed altezza h1, e B2con n2 nodi ed altezza h2. Assumendo che tutti gli elementi in B1 siano minori di quelli in B2, descrivere un algoritmo A che fonda gli alberi B1 e B2 in un unico albero binario di ricerca B di n1+ n2 nodi.
Determinare l’altezza dell’albero B e la complessità computazionale di A.
SOLUZIONE.
La prima idea che si può provare a perseguire è quella di inserire nell’albero con il maggior numero di nodi (senza perdere di generalità sia esso B1) i nodi dell’altro albero uno ad uno. Sapendo che l’operazione di inserimento in un albero binario di ricerca ha una complessità temporale dell’ordine dell’altezza dell’albero si ha, nel caso peggiore, che la complessità è (h1)+O(h1+1)+…O(h1+n2)= n2(h1)+O(1+2+…+n2). Poiché nel caso peggiore (h1)=O(n1)ed O(1+2+…+n2)=O(n22), si ottiene che la complessità di questo approccio è O(n1n2) + O(n22) = O(n1n2), essendo per ipotesi n1>n2. Tuttavia, questa soluzione non utilizza l’ipotesi che tutti gli elementi di B1 siano minori di quelli di B2. Per tentare di sfruttare questa ipotesi (è buona norma tenere presente che se un’ipotesi c’è allora serve a qualcosa!) possiamo pensare di appendere l’intero albero B1 come figlio sinistro del minimo di B2. Questo si può sempre fare facilmente perché il minimo di un albero binario di ricerca è per definizione il nodo più a sinistra che non possiede figlio sinistro, pertanto è sufficiente settare un puntatore sulla radice di B2, scendere verso il figlio sinistro finché esso esista e, giunti all’ultimo nodo (che è il minimo), agganciare a sinistra la radice di B1. Osserviamo che questo procedimento è corretto perché un albero binario di ricerca NON è necessariamente bilanciato, e quindi poco importa che l’altezza dell’albero risultante possa diventare O(h1+h2). La complessità di questo approccio è dominata dalla complessità della ricerca del massimo cioè da O(h1) ed è, pertanto, da preferirsi al primo metodo proposto.
Nessun commento:
Posta un commento