albero generale di binario di conversione albero complessità

Question

Qual è il tempo e lo spazio complessità della conversione di un albero generale ad un binario?!

Grazie

Answer 1

Non so che cosa si intende per "albero generale". Indipendentemente, la complessità tomo di inserimento in un albero binario bilanciato è O(log n), dove n è il numero di elementi attualmente nella struttura, quindi la costruzione di un albero completo da qualche lista di elementi sarebbe O(n log n), dove n è il numero totale di elementi da essere inserito.

avrete anche includere il tempo necessario per ottenere elementi dal lato albero. Quella volta dipende dal tipo di albero che avete. Per amor di discussione darò per scontato che si può attraversare in tempo lineare, in modo da ottenere i dati dalla struttura esistente è O(n).

che rende il vostro O(n + (n log n)) tempo totale complessità.

spazio aggiuntivo richiesto sarà n * sizeof(node), dove sizeof(node) è la dimensione del nodo albero binario. Si noti che, se gli articoli che sono memorizzati nei nodi "albero generale" sono puntatori, non dovrete pagare il costo di copiare gli oggetti reali - solo l'overhead del nodo albero binario, che in genere è di tre indicatori: il i dati, il collegamento figlio sinistro, e il collegamento figlio destro.