Perché non è possibile ricreare un albero AVL utilizzando l'attraversamento pre-ordine?

Question

Perché non è possibile ricreare un albero AVL utilizzando l'attraversamento pre-ordine?

#1 da (5 voti)

0

Dato un albero di ricerca binario, capisco perché posso usare la traversata in ampiezza e in preordine per elencare le voci dell'albero in modo tale da ricostruire l'albero nell'ordine in cui è attraversato.

Tuttavia, se ora consideriamo un albero AVL e vogliamo attraversare l'albero in modo tale da ricreare lo stesso albero AVL (simile a quello che abbiamo fatto con l'albero binario normale) allora perché la larghezza prima di attraversare funziona sempre e perché il preordino non funziona con questo caso dato che funziona con alberi binari standard?

algorithms trees binary-tree

posta rrazd 25.02.2012 - 03:10

fonte

1 risposta

Leggi altre domande sui tag algorithms trees binary-tree

Design dell'oggetto in cui vengono utilizzati valori codificati per creare un'istanza di oggetti? memorizzazione dei dati Javascript [chiuso]

score 5 · Accepted Answer

A differenza di un semplice albero binario, gli alberi AVL sono autobilanciati . Quando un elemento viene inserito in un albero AVL, l'albero potrebbe dover eseguire rotazione dei nodi per mantenere un certo profondità dell'albero, che consente il tempo di ricerca logaritmico. Pertanto, se si tenta di creare un secondo albero AVL utilizzando l'attraversamento del nodo preordinato su un albero AVL esistente, l'albero risultante non avrà necessariamente la stessa struttura nodo, poiché potrebbe essere necessario eseguire rotazioni nodo per mantenere l'albero bilanciato .