Concatenando / fusione / Unione di due alberi AVL
-
19-09-2019 - |
Domanda
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.
Soluzione
Supponendo che si può distruggere gli alberi di ingresso:
- 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)
- 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}
- 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:
- determinare l'altezza di entrambi gli alberi. O (log n)
Partendo dal presupposto che l'albero giusto è più alto (l'altro caso è simmetrica): - rimuovere l'elemento più a destra dall'albero
left
(girevole e regolando l'altezza calcolata se necessario). Lasciaten
essere quell'elemento. O (log n) - Nella struttura di destra, traversi a sinistra fino a raggiungere un nodo il cui sottoalbero è al massimo un 1 più alto di
left
. Lasciater
sia tale nodo. O (log n) -
sostituire tale nodo con un nuovo nodo con il valore n, e sottoalberi
left
er
. O (1)
Per costruzione, il nuovo nodo è AVL equilibrato, e il suo sottoalbero 1 alto dir
. -
incremento del bilanciamento del suo genitore di conseguenza. O (1)
- e riequilibrare come si farebbe dopo aver inserito. O (log n)
Altri suggerimenti
Una soluzione ultra semplice (che funziona senza alcuna ipotesi nelle relazioni tra gli alberi) è questo:
- Fare un merge sort di entrambi gli alberi in un array fusione (in concomitanza iterare entrambi gli alberi).
- 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.
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
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.