Nel post precedente, abbiamo discusso l’introduzione agli alberi Red-Black. In questo post, si discute l’inserimento. Nell’inserimento dell’albero AVL, abbiamo usato la rotazione come strumento per fare il bilanciamento dopo l’inserimento. Nell’albero Red-Black, usiamo due strumenti per fare il bilanciamento.
- Recolorazione
- Rotazione
Recolorazione è il cambiamento del colore del nodo, cioè se è rosso allora lo cambia in nero e viceversa. Bisogna notare che il colore del nodo NULL è sempre nero. Inoltre, proviamo sempre a ricolorare prima, se la ricolorazione non funziona, allora passiamo alla rotazione. Segue un algoritmo dettagliato. L’algoritmo ha principalmente due casi a seconda del colore dello zio. Se lo zio è rosso, ricoloriamo. Se lo zio è nero, facciamo delle rotazioni e/o ricolorazioni.
La rappresentazione con cui lavoreremo è:
Questa rappresentazione è basata su X
Logica:
Per prima cosa, bisogna inserire il nodo in modo simile a quello di un albero binario e assegnargli un colore rosso. Ora, se il nodo è un nodo radice, allora cambia il suo colore in nero, ma se non lo è, controlla il colore del nodo padre. Se il suo colore è nero allora non cambiare il colore ma se non lo è, cioè è rosso, allora controlla il colore dello zio del nodo. Se lo zio del nodo ha un colore rosso allora cambiate il colore del genitore e dello zio del nodo in nero e quello del nonno in rosso e ripetete lo stesso processo per lui (cioè il nonno).
Ma, se lo zio del nodo ha colore nero allora ci sono 4 casi possibili:
- Caso sinistro sinistro (rotazione LL):
- Caso sinistro destro (rotazione LR):
- Caso destro destro (rotazione RR):
- Caso destro sinistro (rotazione RL):
Ora, dopo queste rotazioni, se i colori dei nodi non sono corrispondenti allora ricolorali.
Algoritmo:
Lascia che x sia il nuovo nodo inserito.
- Esegui l’inserimento standard BST e rendi il colore dei nuovi nodi inseriti ROSSO.
- Se x è la radice, cambia il colore di x in NERO (l’altezza nera dell’albero completo aumenta di 1).
- Fai come segue se il colore del genitore di x non è NERO e x non è la radice.
a) Se lo zio di x è ROSSO (Il nonno deve essere stato nero dalla proprietà 4)
(i) Cambia il colore del genitore e dello zio in NERO.
(ii) Cambia il colore di un nonno in ROSSO.
(iii) Cambiare x = il nonno di x, ripetere i passi 2 e 3 per il nuovo x.b) Se lo zio di x è NERO, allora ci possono essere quattro configurazioni per x, il genitore di x (p) e il nonno di x (g) (Questo è simile all’albero AVL)
(i) Caso sinistro sinistro (p è figlio sinistro di g e x è figlio sinistro di p)
(ii) Caso sinistro destro (p è figlio sinistro di g e x è il figlio destro di p)
(iii) Caso destro destro (specchio del caso i)
(iv) Caso sinistro destro (specchio del caso ii)
Esempio: Creazione di un albero rosso-nero con elementi 3, 21, 32 e 17 in un albero vuoto.
Soluzione:
Quando viene inserito il primo elemento viene inserito come nodo radice e come nodo radice ha colore nero quindi acquisisce il colore nero.
Il nuovo elemento viene inserito sempre con colore rosso e come 21 > 3 quindi diventa parte del sottoalbero destro del nodo radice.
Ora, inserendo 32 vediamo che c’è una coppia padre-figlio rossa che viola la regola dell’albero Rosso-Nero quindi dobbiamo ruotarla. Inoltre, vediamo le condizioni della rotazione RR (considerando il nodo nullo del nodo radice come nero) quindi dopo la rotazione come il nodo radice non può essere Rosso quindi dobbiamo eseguire la ricolorazione nell’albero risultante nell’albero mostrato sopra.
Ora quando inseriamo il nuovo elemento il genitore e il nodo figlio con colore rosso appaiono di nuovo e qui dobbiamo ricolorarli. Vediamo che sia il nodo genitore che il nodo zio hanno il colore rosso quindi cambiamo semplicemente il loro colore in nero e cambiamo il colore del nonno in rosso. Ora, poiché il nonno è il nodo radice, cambiamo di nuovo il suo colore in nero, ottenendo l’albero mostrato sopra.
Struttura finale dell’albero:
L’albero finale sarà simile a questo
Si prega di fare riferimento al programma C per l’inserimento dell’albero rosso-nero per l’implementazione completa dell’algoritmo di cui sopra.
Albero Rosso-Nero | Set 3 (Elimina)