Come eliminare un nodo dall'albero BST con 2 bambini?

Question

I Googleò, leggi diversi tutorial e ho guardato diverse spiegazioni dell'algoritmo della cancellazione del nodo BST prima di pubblicare questa domanda. Per qualche motivo, non riesco a trovare una spiegazione completa degli algoritmi della cancellazione del nodo BST.

Ho trovato 4 algoritmi per rimuovere il nodo con 2 bambini dall'albero di ricerca binario:
1) Trova il nodo più piccolo dall'albero secondario destro e sostituirlo con il nodo che vogliamo cancellare.
2) Trova il nodo più grande dall'albero secondario sinistro e sostituirlo con il nodo che vogliamo cancellare.
3) Trova il nodo più profondo a sinistra dall'albero secondario destro e sostituirlo con il nodo che vogliamo cancellare.
4) Trova il nodo più profondo più a destra dall'albero secondario sinistro e sostituirlo con il nodo che vogliamo cancellare.

Apparentemente, nessuno di questi algoritmi funziona per il prossimo caso dell'uso (molto probabilmente perché mi manca o non capisco qualcosa). Il caso d'uso è quello di rimuovere l'elemento 5 dal prossimo albero:

Per il primo algoritmo avremmo scelto l'elemento 6 e perderebbe la sua destra destra. Per il secondo algoritmo avremmo scelto l'elemento 4 e perderebbe il suo albero secondario sinistro. Per il terzo algoritmo abbiamo scelto l'elemento 7 e che viozzerebbe le regole BST. Per il 4 ° algoritmo avremmo scelto Element 3 che viozzerebbe anche le regole BST.

Qual è l'algoritmo giusto per un caso del genere?

Answer 1

Hai ragione, in BST di solito il caso in cui un nodo ha due bambini è ridotto nel caso in cui un nodo ha un figlio.

Considera un nodo con due figli. Scambia questo nodo con il suo predecessore nel BST (cioè il nodo più a destra nel sottosuolo sinistro), o --totally simmetrico: scambia con il successore (il nodo più a sinistra nel sottosuolo destro).

Il nodo da rimuovere ora ha al massimo un figlio (nel caso in cui siamo andati per il predecessore non può avere un figlio destro). Se non ha figli eliminiamo il nodo, e abbiamo finito.

Nel caso in cui il nodo abbia un figlio singolo, rimuoviamo il nodo e lo sostituiamo per la sua sottostruttura. Otteniamo di nuovo un BST.

Nel tuo esempio vogliamo rimuovere 5 e scambiarlo con il suo predecessore 4. Ora 4 è nella radice, e 5 ha lasciato figlio 3. Finalmente rimuoviamo 5 e mettiamo il suo figlio 3 al suo posto. Ora 3 è il figlio giusto di 2.

PS. Questo metodo è talvolta chiamato "cancellazione copiando", poiché i valori vengono copiati da un nodo all'altro. Alcuni non approvano questo processo per due motivi. La prima copia potrebbe essere un'operazione costosa, e i secondi riferimenti vengono persi (se un altro tasstruttura punta a un nodo con un determinato valore). Invece uno cambia solo i puntatori.