PDA

Visualizza la versione completa : [qualsiasi] Cancellazione cu Albero red black


810106
20-06-2008, 05:03
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:



[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:



[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?

810106
20-06-2008, 11:29
Risolto, si applica il caso 6 con una rotazione a sinistra sul padre del nodo da eliminare e si scambiavano i colori del padre con il vecchi fratello colorando il suo figlio destro di rosso... ;)

Loading