Cancellazione in un albero di ricerca binario

Question

L'insegnante ci ha spiegato questo algoritmo per l'eliminazione di un nodo in un albero di ricerca binario, ma non riesco a capire come funziona quando il nodo da eliminare ha un solo figlio (so già come funziona teoricamente). .

Algoritmo:

abc_delete(T, z) // z is the node that must be eliminated 
{
        if((z.left == NULL) && (z.right == NULL))
                y = z;
        else
                y = abr_successor(z);

        if(y.left != NULL)
                    x = y.left;
        else
                    x = y.right;

        if(x != NULL)
                x.p = y.p;

        if(y.p == NULL)
                T.root = x;
        else
        {
                if(y == (y.p).left)
                        (y.p).left = x;
                else
                        (y.p).right = x;
        }

        if(y != z)
                z.key = y.key;
        return y;
}

abr_successor(x)
{
        if(x == NULL)
                return NULL;
        if(x.right != NULL)
                return abr_min(x.right)
        y = x.p;
        while(y != NULL && x == y.right)
        {
                x = y;
                y = y.p;
        }
        return y;
}

.

Ad esempio, voglio eliminare il numero del nodo $ 7 $ :

Ma, non dovrebbe il risultato finale essere questo?

Answer 1

La scelta è certamente corretta.

Tuttavia, non c'è niente di sbagliato nel codice del tuo insegnante, neanche. Ecco un estratto da CLRS.

.

Le operazioni di inserimento e cancellazione causano il set dinamico rappresentato da un albero di ricerca binario da modificare. La struttura dei dati deve essere modificata per riflettere questa modifica, ma in modo tale che la proprietà dell'albero di ricerca binario continua a tenere.

Preferiamo certamente che l'operazione sia effettuata nel modo più semplice o nel modo più veloce. Tuttavia, non vi è alcun requisito La modifica deve essere effettuata nel modo più semplice o anche in modo semplice. Né richiede che la modifica sia effettuata nel modo più veloce o addirittura in qualsiasi modo veloce. Tutto ciò richiede che il funzionamento della cancellazione dovrebbe produrre un altro albero di ricerca binario che ha tutti i nodi dall'albero di ricerca binario specifico senza tale nodo specifico (e non più nodi). Come quei nodi rimanenti formano un albero di ricerca binario è completamente privo di restrizioni.

Il codice del tuo insegnante, d'altra parte, è probabilmente il codice chiaro più breve che fa il lavoro. Più lo studio, più ingenuità che trovo.

Answer 2

Il tuo disegno è la soluzione corretta, tuttavia la tua analisi del tuo codice insegnante non è accurata (U MIS intersetato il codice)

Quando ho visto per la prima volta il Qi non ha letto completamente il codice e pensavo (dal primo PIC / disegno) il tuo insegnante sta eseguendo un'operazione di cancellazione per un tipo speciale di BST che ha condizioni aggiuntive rispetto all'ordine relativo, ma Questo non è il caso

Quando si eliminano da A BST (tentando di seguire le variabili del codice UR, Z è il nodo da eliminare)

Se z è un nodo foglia (nessun bambino) sostituisci solo il puntatore genitore con null

Se Z ha 1 figlio (a sinistra oa destra non importa) rendono il puntatore del genitore al suo unico figlio

È una codifica molto semplice, in un codice semi pseudo

if (z.left== null) {fisico_delete (z, tall); ritorno(); // O abbiamo solo il sottenne o nessuno }

// Qui siamo sicuri che ci sia una sottostruttura sinistra

if (z. destra== null) {fisico_delete (z, z.left); ritorno(); }

// Physy_Delete ha la sostituzione del 2 ° parametro, tutti i loop nel codice del tuo insegnante è scoprire cosa è in grado di avere due sottosuolo

Se Z ha 2 figli, allora devi eleggere uno di loro per prendere il suo posto, ed ecco il codice dell'insegnante (non nel caso precedente)

In Ur Pic Immagina U R Eliminazione "5" Questo codice lungo è per la regolazione del restante sottosuolo dei suoi 2 figli (come collegare 7 e 3 e i loro figli al nodo 12 mantenendo il BST vincolatore)

Se hai bisogno di una traccia dettagliata, possiamo farlo, ma solo se hai trovato utile come inizio