Unire alberi binari

1

Supponiamo di avere una serie di alberi binari con i loro attraversamenti in ordine e preordinato dati e dove nessun albero è una sottostruttura di un altro albero nel set dato. Ora viene fornito un altro albero binario Q.

Scopri se può essere formato unendo gli alberi binari dal set dato (mentre unire ciascun albero nel set dovrebbe essere considerato al massimo una volta). In questo caso, un'operazione di unione significa: Scegli la radice di qualsiasi albero nel set e agganciala a qualsiasi vertice di un altro albero in modo che l'albero risultante sia anche un albero binario.

Possiamo farlo usando LCA (antenato meno comune)? O ha bisogno di qualche datastruttura speciale da risolvere?

    
posta radha 15.04.2016 - 16:23
fonte

1 risposta

1

Da quello che so non c'è modo come hai detto di agganciare il vertice ad un nodo. ciò che puoi fare è prendere gli elementi dall'albero più piccolo e inserirli in quello più grande (metodo lungo)

O

Puoi eseguire l'attraversamento ininterrotto del primo tree store in array1 per il tempo O (n). Applicare lo stesso per il 2 ° albero e memorizzare in tempo array2 O (n). Questi 2 array sarebbero stati ordinati uno e quindi unirli avrebbe anche richiesto il tempo O (n). E poi usa questo array ordinato per costruire BST anche questo richiederà O (n).

Quindi nel complesso ci vuole O (n) tempo.

Puoi cercare su geeksforgeeks per lo stesso.

    
risposta data 20.04.2016 - 20:25
fonte

Leggi altre domande sui tag