Salve a tutti, sto cercando di imparare come funziona un albero red
black ma non riesco a capirmi con gli algoritmi per la cancellazione,
ho guardato wikypedia ma i conti non mi tornano...
Esattamente, io ho questo albero:
codice:
[BLACK]
|
+----------+----------+
| |
[BLACK] [RED]
|
^ +-----+-----+
| | |
nodo da [BLACK] [BLACK]
cancellare |
+--+--+
| |
[RED] [RED]
Ora, secondo quello che c'è scritto su wiky questa cancellazione
rispetta il caso 2. Quindi dovrei scambiare il colore del padre del
nodo da eliminare con il colore del fretello e poi fare una rotazione
a sinistra sul padre. quindi arriverei a questo:
codice:
[BLACK]
|
+----------+----------+
| |
[RED] [BLACK]
+-----+-----+
| |
[BLACK] [BLACK]
^ |
| +---+---+
nodo da | |
eliminare [RED] [RED]
Il problema è che adesso non so piu cosa devo fare, wiky dice che si
dovrebbe risolvere con uno tra i casi 4, 5 o 6 ma solo l'ultimo piu o
meno rispetta la situazione ma il risultato è un albero con un due
nodi rossi consecutivi quindi non credo sia corretto... Qualcuno mi
spiega dove sbaglio?