Fondiamo due alberi binari di ricerca? (complessità?)
Siano dai due alberi binari di ricerca:
$B_1$ con $n_1$ nodi ed altezza $h_1$
$B_2$ con $n_2$ nodi ed altezza $h_2$
Assumiamo, per semplificare, che $B_1$ ha tutti gli elementi minori di quelli in $B_2$.
Trovare un algoritmo che fonda gli alberi $B_1$ e $B_2$ in un unico ABR $B$ di nodi $n_1 + n_2$.
Determinare l'altezza dell'albero trovato e discutere, in modo esaustivo, la complessità dell'algoritmo.
Posso dire di aver pensato di "versare" i nodi dell'albero con numero minore di nodi nell'albero con numero maggiore di nodi.
Ma dovrei contare i nodi dei due alberi per sapere chi ne ha di più....A saperlo a priori forse sarebbe meglio...
Se inseriamo in un ABR la complessità è data dall'altezza dell'albero che vogliamo "versare" nell'altro. Sbaglio?
(Non saprei definirla in modo formale questa complessità però! Forse un $O(n_1 n_2)$ )
Per la fusione si potrebbe "appendere" l'albero $B_1$ come figlio sinistro dell'elemento più piccolo (e senza altri figli sinistri) in $B_2$?
Non badiamo al bilanciamento quindi anche $O(h_1 + h_2)$
Per fare questo forse dobbiamo cercare il massimo valore in $B_1$ e poi il minimo in $B_2$, di cui sopra?
$B_1$ con $n_1$ nodi ed altezza $h_1$
$B_2$ con $n_2$ nodi ed altezza $h_2$
Assumiamo, per semplificare, che $B_1$ ha tutti gli elementi minori di quelli in $B_2$.
Trovare un algoritmo che fonda gli alberi $B_1$ e $B_2$ in un unico ABR $B$ di nodi $n_1 + n_2$.
Determinare l'altezza dell'albero trovato e discutere, in modo esaustivo, la complessità dell'algoritmo.
Posso dire di aver pensato di "versare" i nodi dell'albero con numero minore di nodi nell'albero con numero maggiore di nodi.
Ma dovrei contare i nodi dei due alberi per sapere chi ne ha di più....A saperlo a priori forse sarebbe meglio...Se inseriamo in un ABR la complessità è data dall'altezza dell'albero che vogliamo "versare" nell'altro. Sbaglio?
(Non saprei definirla in modo formale questa complessità però! Forse un $O(n_1 n_2)$ )
Per la fusione si potrebbe "appendere" l'albero $B_1$ come figlio sinistro dell'elemento più piccolo (e senza altri figli sinistri) in $B_2$?
Non badiamo al bilanciamento quindi anche $O(h_1 + h_2)$
Per fare questo forse dobbiamo cercare il massimo valore in $B_1$ e poi il minimo in $B_2$, di cui sopra?
Risposte
Ciao Giova411 
Secondo me conviene innanzitutto determinare quale dei due alberi ha un numero inferiore di nodi e quale ha invece altezza massima. Poniamo dunque innanzitutto $n = \min \{n_1, n_2\}$ e $h = \max \{h_1, h_2\}$.
Ora se $n_1 \le n_2$ conviene, nell'ordine: visitare $B_1$, determinare l'elemento minimo di $B_2$ (il puntatore al relativo nodo), inserire il nodo corrente di $B_1$ in $B_2$ e continuare tale procedimento finché i nodi visitati di $B_1$ non sono terminati.
Se invece $n_1 > n_2$ allora al contrario si dovrà visitare $B_2$ ed eseguire le operazioni descritte in precedenza in maniera speculare (dovremmo determinare in tal caso di volta in volta il massimo valore di $B_1$ e non il minimo).
La complessità dell'algoritmo sarà data da $O(n \log_2 h)$, dove $n$ ed $h$ sono descritti come in precedenza. Questo perché per ciascun nodo dell'albero con il numero minimo di nodi tra i due dovrò effettuare l'inserimento di ciascun nodo nell'altro albero (che avrà altezza massima tra i due).
Che ne pensi
Secondo me può funzionare.
Secondo me conviene innanzitutto determinare quale dei due alberi ha un numero inferiore di nodi e quale ha invece altezza massima. Poniamo dunque innanzitutto $n = \min \{n_1, n_2\}$ e $h = \max \{h_1, h_2\}$.
Ora se $n_1 \le n_2$ conviene, nell'ordine: visitare $B_1$, determinare l'elemento minimo di $B_2$ (il puntatore al relativo nodo), inserire il nodo corrente di $B_1$ in $B_2$ e continuare tale procedimento finché i nodi visitati di $B_1$ non sono terminati.
Se invece $n_1 > n_2$ allora al contrario si dovrà visitare $B_2$ ed eseguire le operazioni descritte in precedenza in maniera speculare (dovremmo determinare in tal caso di volta in volta il massimo valore di $B_1$ e non il minimo).
La complessità dell'algoritmo sarà data da $O(n \log_2 h)$, dove $n$ ed $h$ sono descritti come in precedenza. Questo perché per ciascun nodo dell'albero con il numero minimo di nodi tra i due dovrò effettuare l'inserimento di ciascun nodo nell'altro albero (che avrà altezza massima tra i due).
Che ne pensi
Secondo me può funzionare.
Secondo me l'aspetto principale da considerare in questo caso è che il primo albero ha tutti gli elementi minori dell'altro.. E' quindi sufficiente aggiungere una radice comune e poi mettere i due alberi come sottoalberi destro e sinistro di questa nuova radice..
Secondo me tu sei un Prof nascosto in altre vesti 
Per quanto riguarda il fatto che gli elementi del primo sono minori del secondo?
Non ci serve a qualcosa? Appendere uno all'altro?
(Forse non ho capito bene. Torno su e rileggo
)
Per quanto riguarda il fatto che gli elementi del primo sono minori del secondo?
Non ci serve a qualcosa? Appendere uno all'altro?
(Forse non ho capito bene. Torno su e rileggo
)
APA GIURO CHE NON HO LETTO IL TUO POST!!! IN CONTEMPORANEA!!!! =)
IL MAESTRO MIO!!!!! =)
IL MAESTRO MIO!!!!! =)
"onlyReferee":
..La complessità dell'algoritmo sarà data da $O(n \log_2 h)$
Only se "appendo" solo $O(h)$ ? che poi sia l'altezza di uno o dell'altro non ci frega?
Che dite?
"apatriarca":
.. E' quindi sufficiente aggiungere una radice comune e poi mettere i due alberi come sottoalberi destro e sinistro di questa nuova radice..
Ma la radice non posso tenere quella di $B_2$ attaccando alla sua sx. (Ci sarà un albero sbilanciato ma corretto. O no?)
Aggancio a sinistra la radice di $B_1$
Forse il max di $B_1$ al min di $B_2$ AIUTO 
"Giova411":
[quote="onlyReferee"]..La complessità dell'algoritmo sarà data da $O(n \log_2 h)$
Only se "appendo" solo $O(h)$ ? che poi sia l'altezza di uno o dell'altro non ci frega?
Che dite?
[...]
[/quote]
Mmh... Non so se funzioni perché per ogni nodo ($n$) hai un inserimento da effettuare (che impiega un tempo pari a $\log_2 h$).
"apatriarca":
Secondo me l'aspetto principale da considerare in questo caso è che il primo albero ha tutti gli elementi minori dell'altro.. E' quindi sufficiente aggiungere una radice comune e poi mettere i due alberi come sottoalberi destro e sinistro di questa nuova radice..
Il problema è che valore mettere per la nuova radice però... In tal caso inoltre avrei comunque un nodo in più rispetto a quelli dei due alberi e quindi non è proprio una fusione vera e propria.
Metto il valore massimo in $B_1$ che sarà la radice del sottoalbero costruito (che poi è l'intero albero $B_1$ con una struttura diversa) a partire dal nodo minimo di $B_2$. Poi a scendere uno dietro l'altro gli elementi di $B_1$ senza badare al bilanciamento... Tipo che sarà sbilanciato nettamente a sinistra 
La radice nuova è la radice di $B_2$
La radice nuova è la radice di $B_2$
Esatto, Giova411
Ovviamente nella versione mia ti ho proposto anche quell'ottimizzazione per l'inserimento (si possono inserire i nodi di $B_1$ in $B_2$ o viceversa in base a quale sia l'albero con più nodi) ma il tuo approccio sicuramente è corretto in linea di massima. Il mio suggerimento nasceva semplicemente dall'osservazione che se ho ad esempio $B_1$ con 50 nodi e $B_2$ con uno solo (la radice) non ha senso inserire i nodi di $B_1$ in $B_2$ ma il viceversa... Sei d'accordo
Ovviamente nella versione mia ti ho proposto anche quell'ottimizzazione per l'inserimento (si possono inserire i nodi di $B_1$ in $B_2$ o viceversa in base a quale sia l'albero con più nodi) ma il tuo approccio sicuramente è corretto in linea di massima. Il mio suggerimento nasceva semplicemente dall'osservazione che se ho ad esempio $B_1$ con 50 nodi e $B_2$ con uno solo (la radice) non ha senso inserire i nodi di $B_1$ in $B_2$ ma il viceversa... Sei d'accordo
Certo che sono d'accordo!!!
Si dovrebbe ipotizzare che il primo abbia più nodi del secondo o viceversa.
Si potrebbero fare gli opportuni controlli e magari inserirli in modo bilanciato col suggerimento tuo!
(TUTTE COSE CHE NON SAPREI IMPLEMENTARE
)Vado a nanna!
Ragazzi siete Super come sempre!!!!!!!!!!!!
"Giova411":
[...]
[...]
Si scherza dai =)
La qualità dei messaggi è di altissimo livello vedendo che aiuti moltissime persone!!!
Si vede che la materia ti appassiona e che ne sai davvero... e non solo in informatica.
A me stai aiutando tantissimo e ti ringrazio!!!
Doma provo a stendere due righe di codice giusto per completare il topic....
SCUSATE GLI OT, COLPA MIA!
La qualità dei messaggi è di altissimo livello vedendo che aiuti moltissime persone!!!
Si vede che la materia ti appassiona e che ne sai davvero... e non solo in informatica.
A me stai aiutando tantissimo e ti ringrazio!!!
Doma provo a stendere due righe di codice giusto per completare il topic....
SCUSATE GLI OT, COLPA MIA!
Rispondo di fretta che sono in vacanza.. La radice va ovviamente scelta tra il maggiore dell'albero 'minore' e il minore dell'altro. In questo modo si ottimizza rispetto ai tempi, se si vuole qualcosa di bilanciato come risultato finale conviene usare altri approcci che saranno però meno efficienti come complessità finale.
Apa anche in ferie ti stresso!!!!
Buongiorno ragazzi magici!!
Ieri ho la sensazione d'aver messo un'immagine sbagliata di fusione
O no?
Forse la fusione più veloce la possiamo immaginare così:
Dopo spero di ragionare sullo pseudocodice
Buongiorno ragazzi magici!!
Ieri ho la sensazione d'aver messo un'immagine sbagliata di fusione
O no?
Forse la fusione più veloce la possiamo immaginare così:
Dopo spero di ragionare sullo pseudocodice
Ma alla fine non c'é tanto da scrivere per la fusione semplice?
Complessità? Somma delle due altezze come da disegno:
$O(h_1 + h_2)$
Io la farei così:
Non so se è giusta o troppo sbrigativa.
La sfida potrebbe essere progettare l'algoritmo di Only come variante di risoluzione
Complessità? Somma delle due altezze come da disegno:
$O(h_1 + h_2)$
Io la farei così:
TREE fusioneveloce(TREE b1, TREE b2)
while b2.left != nil do
b2 <-- b2.left
b1.parent <-- b2
return b2
Non so se è giusta o troppo sbrigativa.
La sfida potrebbe essere progettare l'algoritmo di Only come variante di risoluzione
L'altro metodo è diverso e forse avevo azzeccato la complessità nel caso peggiore
Facciamo finta che $B_1$ ha più nodi rispetto a $B_2$ ossia $n_1 >n_2$
Se inseriamo nodo per nodo paghiamo l'altezza del primo ogni volta che inseriamo un nodo del secondo:
$O(h_1) + O(h_1+1) + .. + O(h1+n_2) = O(h_1) * n_2$ se $O(h_1)=O(n_1)$ si potrebbe scrivere anche $O(n_1 n_2)$
Spero di chiudere il topic per i posteri con un bel [risolto]
"Giova411":
(Non saprei definirla in modo formale questa complessità però! Forse un $O(n_1 n_2)$ )
Facciamo finta che $B_1$ ha più nodi rispetto a $B_2$ ossia $n_1 >n_2$
Se inseriamo nodo per nodo paghiamo l'altezza del primo ogni volta che inseriamo un nodo del secondo:
$O(h_1) + O(h_1+1) + .. + O(h1+n_2) = O(h_1) * n_2$ se $O(h_1)=O(n_1)$ si potrebbe scrivere anche $O(n_1 n_2)$
Spero di chiudere il topic per i posteri con un bel [risolto]
[size=85]Aspetto conferma dei post sovrastanti. Di solito, quando APA non interviene, vuol dire che è corretto
[siccome è in ferie.... potrebbe essere tutto cannato pure
][/size]
Ora spero di seguire i suggerimenti di ONLY e fare una fusione un po' più bilanciata!
Però non voglio contare i nodi nei preliminari della fusione...
Ispirazione ONLY ma anche il Merge di Mergesort.
Ho messo come radice del nuovo albero l'elemento mediano $CHIAVI[m]$
Se è come il Merge posso dire che la complessità è lineare!!! $O(n_1 + n_2)$
[siccome è in ferie.... potrebbe essere tutto cannato pure
][/size]Ora spero di seguire i suggerimenti di ONLY e fare una fusione un po' più bilanciata!
Però non voglio contare i nodi nei preliminari della fusione...
TREE Costruisci_Only(integer[] CHIAVI, integer[] VALORI, integer k, integer j)
integer m <-- (k+j)/2
TREE T = new TREE(CHIAVI[m], VALORI[m])
T.left = Costruisci_Only(CHIAVI, VALORI, k, m-1)
T.right = Costruisci_Only(CHIAVI, VALORI, m+1, j)
return T
---
TREE fondialberi(TREE T1, TREE T2)
TREE Ti <-- min(T1)
TREE Tj <-- min(T2)
integer[] CHIAVI
integer[] VALORI
integer k = 1
while ( Ti != nil and Tj != nil) do
if ( Ti.key < Tj.key ) then
CHIAVI[k] = Ti.key
VALORI[k] = Ti.value
Ti = successorNode(Ti)
else
CHIAVI[k] = Tj.key
VALORI[k] = Tj.value
Tj = successorNode(Tj)
k++
while ( Ti != nil and Tj = nil) do
CHIAVI[k] = Ti.key
VALORI[k] = Ti.value
Ti = successorNode(Ti)
k++
while ( Ti = nil and Tj =! nil) do
CHIAVI[k] = Tj.key
VALORI[k] = Tj.value
Tj = successorNode(Tj)
k++
k=k-1
return Costruisci_Only(CHIAVI, VALORI, 1, k)
Ispirazione ONLY ma anche il Merge di Mergesort.Ho messo come radice del nuovo albero l'elemento mediano $CHIAVI[m]$
Se è come il Merge posso dire che la complessità è lineare!!! $O(n_1 + n_2)$
"Giova411":
[...]
Se inseriamo nodo per nodo paghiamo l'altezza del primo ogni volta che inseriamo un nodo del secondo:
[...]
No, paghiamo (e si può dimostrare) per il logaritmo in base due dell'altezza con l'inserimento (sempre considerando il caso peggiore).
"Giova411":
[...]
Ho messo come radice del nuovo albero l'elemento mediano $ CHIAVI[m] $
Se è come il Merge posso dire che la complessità è lineare!!! $ O(n_1 + n_2) $
Ci avevo pensato inizialmente al mergesort soltanto che il merge come sai lavora su array e non su alberi purtroppo
. Toccherebbe pertanto visitare gli alberi (già ordinati), portare i rispettivi nodi in un array di dimensione $n_1 + n_2$, ordinare tutto l'array e costruire l'albero risultante. L'ordinamento però in tal caso ti serve solo se vuoi costruire una struttura del tipo max heap/min heap ma non molto se vogliamo ottenere un albero binario. Banalmente infatti per questo dovresti scorrere dall'inizio alla fine il vettore appena ordinato ed inserire gli elementi in un nuovo albero. Ciò aumenterebbe notevolmente (ed inutilmente a mio avviso) la complessità spaziale...
Buongiorno miei ISTRUTTORI DI VITA!
GRAZIE Only,
hai perfettamente ragione, volevo bilanciare la struttura in qualche modo e senza considerare che in uno ci sono elementi inferiori rispetto all'altro.
Il codice dove appendiamo e basta (by the way: mi confermi che è giusto?) mi sembrava troppo [size=85]stitico [/size]
[size=50]Per la complessità spaziale ho sempre problemini a capirla al volo [/size]
GRAZIE Only,
hai perfettamente ragione, volevo bilanciare la struttura in qualche modo e senza considerare che in uno ci sono elementi inferiori rispetto all'altro.
Il codice dove appendiamo e basta (by the way: mi confermi che è giusto?) mi sembrava troppo [size=85]stitico [/size]
[size=50]Per la complessità spaziale ho sempre problemini a capirla al volo
[/size]
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo