Concatenando / fusione / Unione di due alberi AVL

Question

Si supponga che ho due alberi AVL e che ogni elemento dal primo albero è più piccolo allora qualsiasi elemento dal secondo albero. Qual è il modo più efficace per concatenare in un unico albero AVL? Ho cercato ovunque ma non ho trovato niente di utile.

Answer 1

Supponendo che si può distruggere gli alberi di ingresso:

1. rimuovere l'elemento più a destra per l'albero di sinistra, e usarlo per costruire un nuovo nodo principale, il cui figlio sinistro è la struttura a sinistra, e il cui figlio destro è l'albero giusto: O (log n)
2. determinare e impostare il fattore di equilibrio che del nodo: O (log n). In violazione (temporanea) del invariante, il fattore di equilibrio può essere al di fuori della gamma {-1, 0, 1}
3. ruotare per ottenere il fattore di equilibrio di nuovo in campo: O (log n) rotazioni: O (log n)

In tal modo, l'intera operazione può essere effettuata in O (log n).

Modifica: Il secondo pensiero, è più facile ragionare sulle rotazioni nel seguente algoritmo. E 'anche molto probabile veloce:

1. determinare l'altezza di entrambi gli alberi. O (log n)
   Partendo dal presupposto che l'albero giusto è più alto (l'altro caso è simmetrica):
2. rimuovere l'elemento più a destra dall'albero left (girevole e regolando l'altezza calcolata se necessario). Lasciate n essere quell'elemento. O (log n)
3. Nella struttura di destra, traversi a sinistra fino a raggiungere un nodo il cui sottoalbero è al massimo un 1 più alto di left. Lasciate r sia tale nodo. O (log n)

4. sostituire tale nodo con un nuovo nodo con il valore n, e sottoalberi left e r. O (1)
   Per costruzione, il nuovo nodo è AVL equilibrato, e il suo sottoalbero 1 alto di r.

5. incremento del bilanciamento del suo genitore di conseguenza. O (1)

6. e riequilibrare come si farebbe dopo aver inserito. O (log n)

Answer 2

Una soluzione ultra semplice (che funziona senza alcuna ipotesi nelle relazioni tra gli alberi) è questo:

1. Fare un merge sort di entrambi gli alberi in un array fusione (in concomitanza iterare entrambi gli alberi).
2. Crea un albero AVL dalla matrice - prendere l'elemento centrale per essere la radice, e si applicano in modo ricorsivo a sinistra e metà destra
.

Entrambi i passaggi sono O (n). Il problema principale con esso è che ci vuole O (n) spazio extra.

Answer 3

La soluzione migliore che ho letto a questo problema può essere trovata qui . È molto vicino a risposta Meriton s ' se correggere questo problema:

Nella terza fase dell'algoritmo naviga a sinistra fino a raggiungere il nodo di cui sub albero ha la stessa altezza della struttura a sinistra . Questo non è sempre possibile, (vedi immagine controesempio). Il modo giusto per fare questo passo è di due scoperta per una sottostruttura con h altezza o h+1 dove h è l'altezza della struttura a sinistra

Answer 4

ho il sospetto che non vi resta che andare a piedi un albero (si spera il più piccolo) e individualmente aggiungere ciascuno di esso è elementi per l'altro albero. / eliminare le operazioni AVL insert non sono progettati per gestire l'aggiunta di un'intera sottostruttura alla volta.