Dimostrare numero massimo di giri per due alberi a diventare uguale

Nel libro Introduzione agli algoritmi - un approccio creativo, Domanda 4.24:Dimostrare numero massimo di giri per due alberi a diventare uguale

Let T1 e T2 essere due alberi arbitrari, ciascuno con n nodi . Dimostrare che è sufficiente applicare al massimo 2n rotazioni a T1, in modo che diventi uguale a T2.

Per gli alberi binari di ricerca, ho capito un algoritmo:

trovare l'elemento che è pari a radice di T2, chiamiamolo target-root.
Utilizzando la strategia di rotazione AVL, ruotare target-root per renderlo la nuova radice di T1.
Durante questo processo, possono essere eseguite più rotazioni.
Per l'albero secondario sinistro di T1 e T2, elaborarli come in precedenza in modo ricorsivo.
Per l'albero secondario destro di T1 e T2, elaborarli come in precedenza in modo ricorsivo.

Questo algoritmo, nel caso peggiore, viene eseguito in O (N^2).

Non capisco la frase "alberi arbitrari" e non riesco a capire come rendere T1 uguale a T2.

Qualcuno può aiutare in questa domanda?

fonte

2013-11-24 Guocheng

Non so c'è una risposta semplice. Penso che questo documento sia un buon punto di partenza. Daniel Sleator, Robert Tarjan e William Thurston hanno mostrato che la distanza di rotazione tra due alberi n-nodi (per n ≥ 11) è al massimo 2n - 6, e che infinitamente molte coppie di alberi sono così distanti. http://www.ams.org/journals/jams/1988-01-03/S0894-0347-1988-0928904-4/home.html – amald

@amald grazie, leggerò il documento – Guocheng

Da tutto quello che ho ottenuto che posso proporre un algoritmo in grado di risolvere questo problema in O (N) rotazioni, ma non ha potuto ottenere l'esatto limite superiore, ma pensare di poter costruire su questo: -

Ecco pseudo-codice per l'algoritmo: -

//Method to make T1 equivalent to T2 

    alignTree(T1,T2) { 

    if(length(T1)==1) 
     return 

    else { 

     Node k = FindRoot(T1,T2) 
     rotateAbout(k) 
     align(T1.left,T2.left) 
     align(T1.right,T2.right) 
    } 


    }

Supponiamo FindRoot trova il nodo di T1 che è considerato essere root di nuovo albero che è equivalente albero. Supponiamo che rotateAbout(K) effettui la rotazione appropriata per il root per ottenere nodi equivalenti sui sottoalberi sinistro e destro del nuovo albero. Quindi possiamo risolvere ricorsivamente piccoli problemi secondari su sottostrutture più piccole.

No di rotazioni: Come si può vedere nel codice pseudo il no di rotazione è equivalente a pre-order attraversamento di un albero che è O(N)

Nota: Si può sempre estendere la pseudo codice sopra per l'albero generale e ancora ottengono la stessa complessità.

fonte

2013-11-24 15:31:25

Non penso ruotareInformazioni (K) richiede tempo costante. supponiamo che T1 sia un albero che viene generato inserendo 10,9,8,7,6,5,4,3,2,1, e T2 è un albero che viene generato inserendo 1,2,3,4,5, 6,7,8,9,10. Quindi prima dobbiamo ruotareAbout (1), ci vogliono 9 passi se usiamo la rotazione singola (rotazione singola AVL). – Guocheng

@Guocheng Qui mentre allineiamo i due alberi non corrispondiamo alle chiavi dell'albero ma solo la struttura dei due alberi deve essere la stessa quindi la radice sarà sempre il nodo che ha gli stessi nodi a sinistra ea destra come il secondo albero. Inoltre, non calcoliamo qui la complessità temporale dell'algoritmo ma solo il numero di rotazioni necessario per allineare l'albero. –

quindi come decidere il nuovo nodo radice di T1 e come ruotare per assicurarsi che gli alberi secondari abbiano nodi di numero uguale? – Guocheng

Dimostrare numero massimo di giri per due alberi a diventare uguale

risposta

Problemi correlati