Please enable JavaScript.
Coggle requires JavaScript to display documents.
ALBERI ROSSO NERI - Coggle Diagram
ALBERI ROSSO NERI
DEFINIZIONE
REGOLA 2
RADICE NERA
REGOLA 3
FOGLIE NERE
REGOLA 4
PADRE ROSSO FIGLIO NERO
REGOLA 5
NUMERO NODI NERI DI OGNI NODO FINO ALLE FOGLIE UGUALE
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)
REGOLA 1
OGNI NODO ROSSO O NERO
RB-DELETE
SIMILE ABR
RB-TRANSPLANT
COS'È
UGUALE ABR
SCAMBIA NODI
NON C'È CONDIZIONE v != NIL
RB-DELETE-FIXUP
w = FRATELLO DI x
x = SOSTITUTO DI z
WHILE
x!=T.root && x.color==BLACK
CASI
CASO 1
W.COLOR=RED
SOLUZIONE
LEFT-ROTATE SU x.parent
ASSEGNO w = FRATELLO DI x (w = x.parent.right)
SCAMBIO COLORE w E w.parent
CASO 4
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
CASO 3
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)
CASO 2
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
CASI
CASO 3
z HA 2 FIGLI
SUCCESSORE Z = z.right
CASO 4
z HA 2 FIGLI
SUCCESSORE Z != z.right
CASO 2
z HA 1 FIGLIO
CASO 1
z NON HA FIGLI
z.right = T.nil
z.left = T.nil
z = NODO DA RIMUOVERE
RB-INSERT
COME ABR
RB-INSERT-FIXUP
COS'È
RIMEDIA VIOLAZIONI RB TREE
VIOLAZIONE REGOLA 2
VIOLAZIONE REGOLA 4
CASI INVARIANTE
WHILE: PADRE DI Z ROSSO
CASO 1
COSA SI FA
PADRE DI Z NERO
ZIO DI Z NERO
NONNO DI Z ROSSO
VIOLAZIONE REGOLA 4
ZIO 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