Cancellare tutti i nodi in un albero binario usando O (1) spazio di memoria ausiliario?

Question

L'algoritmo standard per l'eliminazione di tutti i nodi in un binary tree utilizza un postorder traversal sui nodi lungo queste linee:

if (root is not null) { 
    recursively delete left subtree 
    recursively delete right subtree 
    delete root 
} 

Questo algoritmo utilizza O (h) lo spazio di memoria ausiliaria, dove h è l'altezza dell'albero , a causa dello spazio richiesto per memorizzare i frame dello stack durante le chiamate ricorsive. Tuttavia, viene eseguito nel tempo O (n), poiché ogni nodo viene visitato esattamente una volta.

Esiste un algoritmo per eliminare tutti i nodi in un albero binario utilizzando solo O (1) spazio di archiviazione ausiliario senza sacrificare il runtime?

Answer 1

È infatti possibile eliminare tutti i nodi di un albero binario utilizzando O (n) e O (1) spazio di memoria ausiliaria utilizzando un algoritmo basato su tree rotations.

Dato un albero binario con la seguente forma:

  u 
     /\ 
     v C 
     /\ 
     A B 

A destra rotazione di tale albero tira il nodo v sopra il nodo u e determina la seguente struttura:

 v 
    /\ 
     A u 
     /\ 
     B C 

noti che una rotazione dell'albero può essere fatta in O (1) tempo e spazio semplicemente cambiando la radice dell'albero a v, impostando il figlio sinistro di essere l'ex bambino di destra di v, quindi impostando il figlio di destra di te.

Le rotazioni dell'albero sono utili in questo contesto perché una rotazione destra diminuirà sempre l'altezza del sottostruttura di sinistra dell'albero di uno. Ciò è utile a causa di un'osservazione intelligente: è estremamente facile eliminare la radice dell'albero se non ha ancora il figlio di sinistra. In particolare, se l'albero presenta questa forma:

 v 
     \ 
     A 

Quindi possiamo eliminare tutti i nodi dell'albero eliminando il nodo v, quindi eliminare tutti i nodi nel suo sottoalbero A. Questo porta ad una molto semplice algoritmo per l'eliminazione di tutti i nodi dell'albero:

while (root is not null) { 
    if (root has a left child) { 
     perform a right rotation 
    } else { 
     delete the root, and make the root's right child the new root. 
    } 
} 

Questo algoritmo utilizza chiaramente solo o (1) spazio, in quanto necessita al più un numero costante di puntatori per fare una rotazione o per modificare la radice e la lo spazio per questi puntatori può essere riutilizzato attraverso tutte le iterazioni del ciclo.

Inoltre, è possibile dimostrare che questo algoritmo viene eseguito anche in tempo O (n). Intuitivamente, è possibile vedere ciò osservando quante volte un dato spigolo può essere ruotato. Innanzitutto, si noti che ogni volta che viene eseguita una rotazione a destra, un bordo che va da un nodo al figlio sinistro viene convertito in un bordo destro che viene eseguito dal precedente figlio al suo genitore. Quindi, notiamo che una volta che eseguiamo una rotazione che sposta il nodo u come figlio destro del nodo v, non toccheremo mai più il nodo u finché non avremo eliminato il nodo v e tutto il sottostruttura di sinistra di v. Di conseguenza, è possibile limitare il numero di rotazioni totali che verranno mai eseguite notando che ogni bordo dell'albero verrà ruotato al massimo con il suo genitore una volta. Di conseguenza, ci sono al massimo O (n) rotazioni fatte, ognuna delle quali richiede O (1) tempo, e esattamente n cancellazioni fatte. Ciò significa che l'algoritmo viene eseguito nel tempo O (n) e utilizza solo lo spazio O (1).

Nel caso in cui sia utile, ho a C++ implementation of this algorithm, insieme a un'analisi molto più approfondita del comportamento dell'algoritmo.Include anche prove formali di correttezza per tutti i passaggi dell'algoritmo.

Spero che questo aiuti!

Answer 2

Consentitemi di iniziare con una battuta seria: se impostate la radice di un BST su null, eliminate effettivamente tutti i nodi nell'albero (il garbage collector renderà lo spazio disponibile). Mentre il testo è specifico di Java, l'idea vale per altri linguaggi di programmazione. Ne parlo solo nel caso tu fossi in un colloquio di lavoro o durante un esame.

In caso contrario, tutto ciò che dovete fare è utilizzare una versione modificata di DSW algorithm. In pratica, trasforma l'albero in un backbone e poi cancella come se fosse un linked list. Spazio O (1) e tempo O (n). Dovresti trovare discorsi di DSW in qualsiasi libro di testo o online.

Fondamentalmente DSW viene utilizzato per bilanciare un BST. Ma per il tuo caso, una volta ottenuto il backbone, invece di bilanciare, si cancella come se fosse una lista collegata.