Ho due alberi binari e voglio unirli. La mia prima domanda è se possiamo unire due alberi binari e, in caso affermativo, con quale efficienza posso eseguire le operazioni di unione e quali sono i vari modi in cui posso eseguire le operazioni di unione. ..?Come posso unire due alberi binari
Non considerando l'efficienza questa risposta potrebbe funzionare Algorithm of combining two binary trees?. Se ordinati o bilanciati, discussione sull'efficienza in How to merge two BST's efficiently? e Concatenating/Merging/Joining two AVL trees
1) Appiattire entrambi gli alberi in elenchi ordinati.
2) Unire le liste da quello che avete ottenuto in 1)
3) Costruire l'albero di ciò che avete ottenuto in 2)
è la complessità? –
È possibile appiattire gli alberi in elenchi in tempo O (n) utilizzando una normale camminata in ordine. L'unione di due elenchi ordinati può essere eseguita anche nel tempo O (n). Una volta uniti gli elenchi, puoi costruire il BST nel tempo O (n) costruendo ricorsivamente gli alberi fuori dalle metà sinistra e destra, quindi incollandoli insieme. La complessità complessiva è quindi O (n). – templatetypedef
@templatetypedef: Grazie per la risposta. Sì, la complessità è O (n). – hari
Creare un nuovo nodo e puntare una coda alla testa di uno degli alberi e puntare l'altra coda sulla testa dell'altro albero. Forse hai bisogno di chiarire la tua domanda per essere più specifico. Quali relazioni stai cercando di preservare?
Un albero è anche un grafico, quindi restituire le coppie di vertici del bordo (u, v) per ogni albero, quindi unire questi gruppi di spigoli e generare il grafico risultante.
Il problema si pone con il modo di mappare i vertici nell'un albero ai vertici nell'altro (ad es. Abbiamo una coppia di spigoli (5,9) nell'albero 1 e una coppia di spigoli (5,6) nell'albero 2, facciamo questi 5 corrisponde allo stesso vertice?).
Comando con una numerazione di vertici (forse che assegna numeri a ciascun vertice in un albero binario incompleto, come se fosse un albero binario completo, quindi in altre parole assegna i vertici in qualsiasi albero binario parziale a slot di un l'ipotetico completo albero binario di cui quell'albero è una sottostruttura), che in qualche modo fornisce un'equivalenza desiderabile è qualcosa che funziona.
L'unione di alberi binari è banale, basta collegare la radice di uno come figlio di uno dei nodi foglia dell'altro. Hai avuto qualche altra struttura che vuoi preservare, come essere ordinato o bilanciato? – JGWeissman
consente di iniziare con un albero non bilanciato semplice non ordinato. Hai detto che è banale, quindi puoi solo mostrarmi come è fatto ..? –