Concatenate Alberi binari di ricerca

[jJjjJ1]

Ho questo esercizio, e vorrei sapere se sto procedendo nel modo corretto.

1. Definiamo un'operazione

concatenate

il cui input è costituito da due insiemi $S_1$ e $S_2$ tali che le chiavi di $S_1$ sono tutte minori o uguali alle chiavi di $S_2$ ed il cui output è la fusione dei due insiemi in uno. Progettare un algoritmo per concatenare due alberi binari di ricerca in un albero binario di ricerca. L'algoritmo deve avere tempo di esecuzione $O( h )$ nel caso peggiore, dove $h$ è la massima altezza dei due alberi.

Io ho pensato che sicuramente non posso scorrere uno dei due alberi ed inserire ogni nodo nel secondo, perché ogni inserimento costa $O( h )$ dove h è l'altezza dell'albero di fusione. Quello che ho pensato è che poiché sappiamo che le chiavi del primo albero sono tutte minori o uguali alle chiavi del secondo albero, mi basta trovare il minimo di quest'ultimo, e inserire il primo albero come sottoalbero, l'algoritmo pensato è:

algoritmo concatenate( Alberi A e B )
       u <- radice di B
       while( figlio sx di u != null ) do
              u <- figlio sx di u
       figlio sx di u <- radice di A

Ovviamente si ha che questo algoritmo ha tempo di esecuzione $O( h_2 )$ con $H_2$ altezza del secondo albero. E' corretto?

[apatriarca]

Credo che tu debba considerare il caso in cui il massimo di uno dei due sia uguale al minimo dell'altro. In questo caso avresti un elemento ripetuto nell'albero che dovresti eliminare (o almeno credo).

[jJjjJ1]

In realtà non l'ho considerato perché nel mio libro nella definizione di albero binario di ricerca dice che ogni nodo $v$ ha la proprietà le chiavi del sottoalbero sinistro di $v$ sono $<=$ alla chiave di $v$ e le chiavi del sottoalbero destro sono $>=$ alla chiave di $v$

[apatriarca]

Allora direi che va bene.. Un'alternativa che ha il vantaggio di creare un albero più bilanciato è quella di prendere l'elemento più piccolo del secondo albero e farlo diventare la nuova radice per i due alberi.

[jJjjJ1]

Infatti l'esercizio successivo mi chiede di considerare due alberi AVL, in questo caso ho pensato di prendere il minimo dal secondo albero, toglierlo, metterlo a radice e mettere come sottoalbero sinistro $A$ e come sottoalbero destro $B$. Tuttavia non capisco bene come effettuare il ribilanciamento, perché ovviamente l'albero si sbilancia alla radice, allora ho pensato, supponendo $h_1\ <\ h_2$

-Detto $z$ il figlio destro della radice, e detti $B_1$ e $B_2$ i suoi sottoalberi sinistro e, rispettivamente, destro, si controlla il fattore di bilanciamento di $z$:

1. Se $\beta ( z ) = 0$ oppure $ \beta ( z ) < 0 $ si esegue una rotazione centrata nella radice verso sinistra (siamo nel caso DD)

2. Altrimenti si esegue una rotazione DS

In entrambi i casi la radice cambia e si bilancia, il figlio sinistro della radice è la radice precedente e si ha che il suo fattore di bilanciamento è diminuito di almeno 1 in valore assoluto, iteriamo il procedimento su questo nodo e otteniamo che al più in $O(h_2)$ passi il nodo sarà bilanciato ( caso estremo di un albero A con un solo nodo e albero B AVL binario completo )
Ragionamenti analoghi per il caso opposto. Giusto?

[apatriarca]

Direi che ad una rapida occhiata potrebbe andare bene.