ALBERI ROSSO NERI
DEFINIZIONE
REGOLA 2
REGOLA 3
REGOLA 4
PADRE ROSSO FIGLIO NERO
REGOLA 5
ALTEZZA MASSIMA
2 log(n+1)
DIMOSTRAZIONE
ALTEZZA = h
ALTEZZA NERA = h/2
NUMERO NODI INTERNI n >= 2^(h/2) - 1
h <= 2 log (n+1)
RB-INSERT
COME ABR
RB-INSERT-FIXUP
COS'È
RIMEDIA VIOLAZIONI RB TREE
CASI INVARIANTE
VIOLAZIONE REGOLA 2
VIOLAZIONE REGOLA 4
WHILE: PADRE DI Z ROSSO
CASO 1
COSA SI FA
VIOLAZIONE REGOLA 4
ZIO DI Z ROSSO
PADRE DI Z NERO
ZIO DI Z NERO
NONNO DI Z ROSSO
CASO 2
ZIO DI Z NERO E Z FIGLIO DESTRO
VIOLAZIONE REGOLA 4
COSA SI FA
PONIAMO Z = Z.PARENT
LEFT-ROTATE RISPETTO AL NUOVO Z
Z DIVENTA FIGLIO SINISTRO (CASO 3)
CASO 3
ZIO DI Z NERO E Z FIGLIO SINISTRO
VIOLAZIONE REGOLA 4
COSA SI FA
PONIAMO Z.PARENT NERO
PONIAMO Z.PARENT.PARENT ROSSO
RIGHT-ROTATE RISPETTO A Z.PARENT.PARENT
RB-DELETE
SIMILE ABR
RB-TRANSPLANT
COS'È
UGUALE ABR
SCAMBIA NODI
NON C'È CONDIZIONE v != NIL
REGOLA 1
OGNI NODO ROSSO O NERO
RADICE NERA
FOGLIE NERE
NUMERO NODI NERI DI OGNI NODO FINO ALLE FOGLIE UGUALE
RB-DELETE-FIXUP
CASI
CASO 3
CASO 4
CASO 2
CASO 1
z NON HA FIGLI
z HA 1 FIGLIO
z HA 2 FIGLI
SUCCESSORE Z = z.right
z HA 2 FIGLI
SUCCESSORE Z != z.right
z.right = T.nil
z.left = T.nil
w = FRATELLO DI x
x = SOSTITUTO DI z
z = NODO DA RIMUOVERE
WHILE
x!=T.root && x.color==BLACK
CASI
CASO 1
CASO 4
W.COLOR=RED
CASO 3
CASO 2
SOLUZIONE
LEFT-ROTATE SU x.parent
ASSEGNO w = FRATELLO DI x (w = x.parent.right)
SCAMBIO COLORE w E w.parent
W.COLOR=BLACK && W.RIGHT.COLOR=BLACK && W.LEFT.COLOR = BLACK
SOLUZIONE
W.COLOR=RED
X=X.PARENT
DOPPIO NERO PASSA DA X A X.PARENT
W.COLOR=BLACK && W.RIGHT.COLOR=BLACK && W.LEFT.COLOR = RED
SOLUZIONE
W.LEFT.COLOR=BLACK
W.COLOR=RED
RIGHT-ROTATE SU W
W = FRATELLO DI X (W=X.PARENT.RIGHT)
W.COLOR=BLACK && W.RIGHT.COLOR=BLACK && W.LEFT.COLOR = BLACK
SOLUZIONE
W.COLOR=W.PARENT.COLOR
W.PARENT.COLOR=BLACK
W.RIGHT.COLOR=BLACK
LEFT-ROTATE SU W.PARENT
RIMUOVIAMO NERI IN ECCESSO