Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black.

Algoritmi e Strutture Dati

Alberi Bilanciati: Alberi Red-Black

Alberi Red-Black (alberi rossi-neri)

Un Albero Red-Black (rosso-nero) è essenzialmente un albero binario di ricerca in cui:

1 Le chiavi vengono mantenute solo nei nodi interni dell’albero

2 Le foglie sono costituite da nodi NIL, cioè nodi sentinella il cui contenuto è irrilevante e che evitano di trattare diversamente i puntatori ai nodi dai puntatori NIL. • In altre parole, al posto di un puntatore NIL si

usa un puntatore ad un nodo NIL. • Quando un nodo ha come figli nodi NIL,

quiel nodo sarebbe una foglia nell’albero binario di ricerca corrispondente.

Alberi Red-Black (alberi rossi-neri)Un Albero Red-Black (rosso-nero) deve

soddisfare le seguenti proprietà (vincoli):

1 Ogni nodo è colorato o di rosso o di nero;

2 Per convezione, i nodi NIL si considerano nodi neri;

3 Se un nodo è rosso, allora entrambi i suoi figli

sono neri;

4 Ogni percorso da un nodo interno ad un nodo NIL (figlio di una foglia) ha lo stesso numero di nodi neri;

Alberi Red-Black (alberi rossi-neri)Un Albero Red-Black (rosso-nero) deve

soddisfare le seguenti proprietà (vincoli):

1 Ogni nodo è colorato o di rosso o di nero;

2 Per convezione, i nodi NIL si considerano nodi neri;

3 Se un nodo è rosso, allora entrambi i suoi figli

sono neri;

4 Ogni percorso da un nodo interno ad un nodo NIL (figlio di una foglia) ha lo stesso numero di nodi neri;

Considereremo solo alberi Red-Black in cui la radice è nera.

Alberi Red-Black: esempio I

3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30

NilNil

Nil Nil Nil

Nil Nil NilNil

Nil Nil Nil Nil NilNil

NilNil

Nil Nil Nil

Nil Nil NilNil

Vincolo 3 impone che non possano esserci due nodiROSSI adiacenti. (Ma più nodi NERI possono essere adiacenti.)

NilNil

Nil Nil Nil

Nil Nil NilNil

Ci sono 3 nodi neri lungo ogni percorso dalla radi-ce ad un nodo NIL

Nil Nil NilNil

Questo è anche un albero AVL

3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri.

altezza 2 altezza 3

1 livello di diff.

5 Nil Nil

NilNil

Alberi Red-Black: esempio II

65Nil Nil Nil Nil

Nil Nil NilNil

Questo è ancoraun albero Red-Black

Alberi Red-Black: esempio II

Ma NON è un albero AVL!

65Nil Nil

Nil Nil NilNil

2 livelli

altezza 1 altezza 3

NilNil

Nil Nil Nil

Nil Nil NilNil

Alberi Red-Black: esempio III

NilNil

Nil Nil Nil

Nil Nil NilNil

Alberi Red-Black: esempio IV

50 65Nil Nil Nil Nil

Nil Nil Nil Nil Nil Nil NilNil

Albero RB con 3 nodi neri lungo ogni percorso dalla radice ad un nodo NIL

Alberi Red-Black: esempio V

50 65Nil Nil Nil Nil

Nil Nil Nil Nil Nil Nil NilNil

Stesso albero con 2 nodi neri lungo ogni percorso dalla radice ad un nodo NIL

Alberi Red-Black: esempio VI

50Nil Nil Nil Nil Nil Nil

Questo albero può essere un albero Red-Black?

Nil Nil NilNil

Per vincolo 4 ci possono essere al più 3 nodi neri lungo un percorso!

Nil Nil NilNil

Impossibile!Perché...

Nil Nil NilNil

Impossibile!Perché dovremmo

violare vincolo 3

Nil Nil NilNil

Quindi uno di questidue nodi deve essere

Nil Nil NilNil

Esistono due percorsicon 2 soli nodi neri

Nil Nil NilNil

Esiste un percorsocon 2 soli nodi neri

Nil Nil NilNil

Esiste un percorsocon 2 soli nodi neri

Questo caso èimpossibile perchè

un percorso ha 3 neri

Per vincolo 4 e il vincolo 3, ci possono essere al più 2 nodi neri lungo un percorso!

Nil Nil NilNil

Questa sarebbel’unica possibilità!

Nil Nil NilNil

Impossibile!Perché dovremmo

violare vincolo 4

Questo albero NON può essere un albero Red-Black!

Nil Nil NilNil

A meno che l’albero non venga ristrutturato (tramite rotazioni)

Percorso Nero in alberi Red-Black

Definizione: Il numero di nodi neri lungo ogni percorso da un nodo x (escluso) ad una foglia è detto altezza nera di x

Definizione: L’altezza nera di un albero Red-Black è l’altezza nera della sua radice.

Percorso massimo in alberi Red-Black

Lemma: Un albero Red-Black con n nodi ha altezza al più 2 log(n + 1)

Dimostrazione: Iniziamo col dimostrare per induzione che il sottoalbero con radice x ha almeno

nodi interni

dove bh(x) è l’altezza nera di x.

L’induzione sarà sull’altezza di x.

12 )( xbh

01212 0)( xbh

Il sottoalbero con radice x ha al meno

nodi interni

Passo Base:

Se x ha altezza 0: allora x è una foglia NIL e quindi contiene almeno:

Il sottoalbero con radice x ha al meno

nodi interni

Passo Induttivo:

Se x sia interno con 2 figli e

abbia altezza bh(x)>1

Entrambi i suoi figli avranno

altezza bh(x) o bh(x)-1

12 )( xbh

bh(x)bh(x)-1

bh(x) -1bh(x)-1

Percorso massimo in alberi Red-BlackIl sottoalbero con radice x ha al meno

nodi interni

Passo Induttivo:

Sia x nodo interno con 2 figli

e abbia altezza > 0

altezza nera bh(x) o bh(x)-1

Entrambi i suoi figli avranno altezza

minore di x, quindi possiamo usare ipotesi induttiva

12 )( xbh

bh(x)bh(x)-1

bh(x) -1bh(x)-1

nodi interni

Passo Induttivo:

Se x sia interno con 2 figli e

abbia altezza >0

altezza nera bh(x) o bh(x)-1

Ogni figlio avrà almeno

nodi interni

12 )( xbh

12 1)( xbh

bh(x)bh(x)-1

bh(x) -1bh(x)-1

nodi interni

Passo Induttivo:

Sia x nodo interno con 2 figli e abbia altezza >0

Ogni figlio avrà almeno

nodi interni

Quindi il sottoalbero con radice x conterrà almeno

nodi interni

12 )( xbh

12 1)( xbh

)12(1)12()12( )(1)(1)( xbhxbhxbh

Percorso massimo in alberi Red-BlackIl sottoalbero con radice x ha quindi al meno

nodi interni

Completiamo la dimostrazione del lemma.

Sia ora h l’altezza dell’albero.

Per il vincolo 3 almeno metà dei nodi lungo ogni percorso (esclusa la radice) sono neri.

Quindi l’altezza nera dell’albero dovrà essere almeno h/2 ( cioè bh h/2 ).

12 )( xbh

nodi interni

Quindi l’altezza nera dell’albero dovrà essere almeno h/2 ( cioè bh h/2 ).

Ma allora, il numero di nodi dell’albero sarà

12 )( xbh

12)12( 2)( hxbhn

Percorso massimo in alberi Red-BlackLemma: Un albero Red-Black con n nodi ha

altezza al più 2 log(n + 1)

Dimostrazione: ….

Ma allora, il numero di nodi dell’albero sarà

Portando 1 a sinistra e applicando il logaritmo:

12)12( 2)( hxbhn

2)1log( hn )1log(2 nh

Costo operazioni su alberi Red-Black

Teorema: In un albero Red-Black le operazioni di ricerca, inserimento e cancellazione hanno costo O(log(n)).

Dimostrazione: Conseguenza diretta del Lemma precedente e dal fatto che tutte le operazioni hanno costo O(h), con h l’altezza dell’albero.

Violazione delle proprietà per inserimento

• Durante la costruzione di un albero Red-Black, quando un nuovo nodo viene inserito è possibile che le condizioni di bilancia-mento risultino violate.

• Quando le proprietà Red-Black vengono violate si può agire:

• modificando i colori nella zona della violazione;

• operando dei ribilanciamenti dell’albero tramite rotazioni: Rotazione destra e Rotazione sinistra;

Alberi Red-Black: Rotazione destra

sinistro

destro

colore

Rotazione col figlio destroRotazione va da destra a sinistraIl libro la chiama Rotazione a Sinistra

Padre del sottoalbero

sinistro

destro

colore

Rotazione-destra(T,x : albero-RB) y = destro[x ] destro[x ] = sinistro[y ] IF sinistro[y ] NIL THEN padre[sinistro[y ]] = x padre[y ] = padre[x ] IF padre[x ] = NIL THEN root[T ] = y ELSE IF x = sinistro[padre[x ]] THEN sinistro[padre[x ]] = y ELSE destro[padre[x ]] = y sinistro[y ] = x padre[x ] = y

sinistro

destro

colore

Assunzione:destro[x ] NIL

Alberi Red-Black: Rotazione destraRotazione-destra(T,x : albero-RB) y = destro[x ] destro[x ] = sinistro[y ] IF sinistro[y ] NIL THEN padre[sinistro[y ]] = x padre[y ] = padre[x ] IF padre[x ] = NIL THEN root[T ] = y ELSE IF x = sinistro[padre[x ]] THEN sinistro[padre[x ]] = y ELSE destro[padre[x ]] = y sinistro[y ] = x padre[x ] = y yx

Alberi Red-Black: Rotazione destraRotazione-destra(T,x : albero-RB) y = destro[x ] destro[x ] = sinistro[y ] IF sinistro[y ] NIL THEN padre[sinistro[y ]] = x padre[y ] = padre[x ] IF padre[x ] = NIL THEN root[T ] = y ELSE IF x = sinistro[padre[x ]] THEN sinistro[padre[x ]] = y ELSE destro[padre[x ]] = y sinistro[y ] = x padre[x ] = y

Inserimento in alberi Red-Black

Inseriamo un nuovo nodo x usando la stessa procedura usata per gli alberi binari di ricerca

Coloriamo il nuovo nodo di rossoCi spostiamo verso l’alto lungo il percorso di

inserimento per ripristinare la proprietà Red-Black:spostiamo le violazioni verso l’alto rispettando il

vincolo 4 (mantenendo l’altezza nera dell’albero)Al termine, coloriamo la radice di nero.

Le operazioni di ripristino sono necessarie solo quando due nodi consecutivi sono rossi!

Inserimento in alberi Red-Black

Le operazioni di ripristino sono necessarie solo quando due nodi consecutivi sono rossi!

Se la radice è sempre nera, non si presenta mai la necessità di ribilanciare l’albero lungo percorsi che contengono meno di tre nodi!

Non si possono, infatti, verificare violazioni!

Nil Nil

6Nodo da inserire

Radice Radice

Ribilanciamenti: casi 1-3

caso 1

Caso 1: il figlio y del padre del padre di x è rosso

x è il nodo modificato che provoca lo sbilanciamento Red-Black

y è il figlio del padre del padre di x

caso 1

caso 2

Questa radiceè nera

Caso 2: il figlio y del padre del padre di x è nero x è un filgio destro

caso 1

caso 2caso 3

La radice diy è neraLa radice di

y è nera

Caso 3: il figlio y del padre del padre di x è nero x è un filgio sinistro

Inserimento in alberi RB: Caso 1Caso 1: il figlio y del

padre del padre di x è rosso

Tutti i sono sottoalberi di uguale altezza nera

Cambiamo i colori di alcuni nodi, preservando vincolo 4: tutti i percorsi sotto a questi nodi hanno altezza nera uguale.

Poi si continua verso l’alto facendo del padre del padre di x il nuovo x

caso 1C

Inserimento in alberi RB: Caso 1y = destro[padre[padre[x]]]

IF colore[y] = ROSSO

THEN colore[padre[x]] = NERO

colore[y] = NERO

colore[padre[padre[y]]] = ROSSO

x = padre[padre[x]]

Cambiamo i colori di alcuni nodi, preservando vincolo 4: tutti i percorsi sotto a questi nodi hanno altezza nera uguale.

colore[y] = NERO

x = padre[padre[x]]

Cambiamo i colori di alcuni nodi, preservando vincolo 4: tutti i percorsi sotto hanno altezza nera uguale.

caso 1y

colore[y] = NERO

x = padre[padre[x]]

Cambiamo i colori di alcuni nodi, preservando vincolo 4: tutti i percorsi sotto hanno altezza nera uguale.

caso 1y

Poiché il padre di C può essere rosso, può essere necessario ripri-stinare la proprietà RB più in alto

Inserimento in alberi RB: Caso 1

Si eseguono le stesse azioni sia quando x è un figlio sinistro o un figlio destro

caso 1

y = destro[padre[padre[x]]]

colore[y] = NERO

x = padre[padre[x]]

Inserimento in alberi RB: Caso 2Caso 2:• il figlio y del padre del padre

di x è nero• x è un filgio destro• Trasformiamo nel caso 3

con una rotazione destra

Trasformiamo il caso 2 nel caso 3 (x è figlio sinistro) con una rotazione destra. Ciò preserva il vincolo 4: tutti i percorsi sotto x

contengonolo stesso numero di nodi neri

caso 2y

IF x = destro[padre[x]]

THEN x = padre[x]

rotazione-destra(T,x)

// continua con caso 3

Caso 2:• il figlio y del padre del padre

A ycaso 2

IF x = destro[padre[x]]

THEN x = padre[x]

rotazione-destra(T,x)

// continua con caso 3

caso 2

Caso 2:• il figlio y del padre del padre

Caso 3:• il figlio y del padre

del padre di x è nero• x è un filgio sinistro• Cambiare colori e

rotazione sinistra

caso 3C

Eseguiamo alcuni cambi di colore e facciamo una rotazione sinistra. Di nuovo, preserviamo il vincolo 4: tutti i

percorsi sotto x contengono lo stesso numero di nodi neri.

colore[padre[x]] = NERO

colore[padre[padre[x]]] = ROSSO

rotazione-sinistra(T,padre[padre[x]])

rotazione sinistra

caso 3C

Questa radiceè nera

rotazione sinistra

caso 3C

yQuesta radice

è nera

rotazione sinistra

Inserimento in alberi RB: Casi 4-6

• I casi 1-3 assumono che il padre di x sia un figlio sinistro

• Se il padre di x è un figlio destro si applicano i casi 4-6 che sono simmetrici (scambiamo sinistro con destro e viceversa).

L’estensione dell’algoritmo ai casi 4-6 è lasciato come esercizio

Inserimento in alberi Red-BlackRB-Inserisci(T,x : albero-RB) ABR-Inserisci(T,x) colore[x] = ROSSO WHILE (x root[T] AND colore[padre[x]] = ROSSO) DO IF padre[x] = sinistro[padre[padre[x]]] THEN y = destro[padre[padre[x]]] IF colore[y] = ROSSO THEN colore[padre[x]] = NERO colore[y] = NERO colore[padre[padre[y]]] = ROSSO x = padre[padre[x]] ELSE IF x = destro[padre[x]] THEN x = padre[x] rotazione-destra(T,x) colore[padre[x]] = NERO colore[padre[padre[x]]] = ROSSO rotazione-sinistra(T,padre[padre[x]]) ELSE {come il THEN ma con destro e sinistro scambiati} colore[root[T]] = NERO

Caso I

Casi II e III

Caso I

Caso II

Caso III

Inserimento in alberi Red-Black: I

65Nil Nil Nil Nil

Nil Nil NilNil

Il padre è NERO, il nuovo nodo x diventa ROSSO

Nil Nil

Inserimento in alberi Red-Black: I

65Nil Nil Nil

Nil Nil NilNil

Il padre è NERO, il nuovo nodo x diventa ROSSONessun Cambiamento

Non cambia l’altezza neradi nessun nodo!

Nil Nil

Inserimento in alberi Red-Black: II

65Nil Nil Nil

Nil Nil NilNil

TSe il padre è ROSSO, il nuovo nodo è ROSSO

Nil Nil

65Nil Nil Nil

Nil NilNil

xVincolo 3 è violato

Caso I: L’altro figlio del padre del padre di x è rosso

Nil Nil

65Nil Nil Nil

Nil NilNil

Nil Nil

•Coloriamo di nero il padre di x

65Nil Nil Nil

Nil NilNil

Nil Nil

•Coloriamo di nero padre di x •Coloriamo di nero il figlio del padre del padre di x

65Nil Nil Nil

Nil NilNil

Nil Nil

•Coloriamo di nero padre di x •Coloriamo di nero il figlio del padre del padre di x•Coloriamo di rosso il padre del padre di x

65Nil Nil Nil

Nil NilNil

Nil Nil

Vincolo 3 è ripristinatoVincolo 4 è ripristinato

Il padre del padre di x è il nuovo x

65Nil Nil Nil

Nil NilNil

Caso III: L’altro figlio del padre del padre di x è nero

Nil Nil

Vincolo 3 è nuovamente violato

tra il nuovo x e suo padre

65Nil Nil Nil

Nil NilNil

Nil Nil

•Coloriamo di nero il padre di x

65Nil Nil Nil

Nil NilNil

Nil Nil

•Coloriamo di nero il padre di x•Coloriamo di rosso padre del padre di x

65Nil Nil Nil

Nil NilNil

Nil Nil

•Coloriamo di nero il padre di x•Coloriamo di rosso padre del padre di x•Rorazione sinistra

40 55 65Nil Nil Nil

Nil NilNil Nil

Nil Nil Nil Nil

Nil Nil

Poiché il padre di x sarà sempre nero, abbiamo finito

Vincolo 3 è ripristinatoVincolo 4 è ripristinato

40 55 65Nil Nil Nil

Nil NilNil Nil

Nil Nil Nil Nil

Nil Nil

L’unico caso un cui si procede a ripristinare verso l’alto è il caso I. Negli altri 2

casi, il padre di x sarà sempre nero, si esce quindi

dal WHILE e si termina

Cancellazione in RB

• L’algoritmo di cancellazione per alberi RB è costruito sull’algoritmo di cancellazione per alberi binari di ricerca

• Useremo una variante con delle sentinelle Nil[T], una per ogni nodo NIL (perché?), per semplificare l’algoritmo

• Dopo la cancellazione si deve decidere se è necessario ribilanciare o meno

• Le operazioni di ripristino del bilanciamento sono necessarie solo quando il nodo cancellato è nero! (perché?)

Cancellazione in RBRB-Cancella(T,z:albero-RB) IF (sinistro[z] = Nil[T] OR destro[z] = Nil[T]) THEN y = z ELSE y = ARB-Successore(z) IF sinistro[y] Nil[T] THEN x = sinistro[y] ELSE x = destro[y] IF x Nil[T] THEN padre[x]=padre[y] IF padre[y] = Nil[T] THEN Root[T] = x ELSE IF y = sinistro[padre[y]] THEN sinistro[padre[y]]=x ELSE destro[padre[y]]=x IF y z THEN “copia i campi di y in z” IF colore[y ] = NERO THEN RB-Fix-Cancella(T,x) return y

caso III

casi I e II

y è il nodo da eli-minare e x è il suo sostituto

y è sostituito da x

Cancellazione in RB

• Dobbiamo ribilanciare se il nodo cancellato è nero (perché è cambiata l’altezza nera)

• Possiamo immaginare di colorare di nero il nodo x che sostituisce il nodo cancellato y

• In tal modo la cancellazione non viola più il vincolo 4 ...

• … ma potrebbe violare il vincolo 1 (perché?)

• L’algoritmo RB-Fix-Cancella(T,x) tenta di ripristinare il vincolo 1 con rotazioni e cambia-menti di colore:• ci sono 4 casi possibili (e 4 simmetrici)

Cancellazione in RB

Il nodo x (cioè A nell’esempio) è bordato di rosso ad indicare che è il nodo con un nero in più da aggiungere (e ridistribuire) nell’albero

Caso 1: fratello rosso, padre nero

Cancellazione in RB

Caso 1: fratello rosso, padre nero

Caso 2

Il nodo c (cioè B nell’esempio) può essere sia rosso che nero!

: fratello nero con figli neri

Cancellazione in RB

Caso 1

Caso 2

Caso 3: fratello nero con figlio sin. rosso

: fratello nero con figli neri

Caso 4: fratello nero con figlio des. rosso

: fratello rosso, padre nero

Cancellazione in RB: caso 1

caso 1

colore[padre[x]] = ROSSOcolore[w] = NEROrotazione-destra(T,padre[x])w = destro[padre[x]]

• Il fratello w di x è rosso• w deve avere figli neri • cambiamo i colori di w e del padre di x e li ruotiamo tra loro

Non violiamo né il vincolo 3 né il 4 e ci riduciamo ad uno degli altri casi

caso 2

colore[w] = ROSSOx = padre[x]

• Il fratello w di x è nero• w ha in questo caso entrambi i figli neri • cambiamo il colore di w e il nuovo x diventa il padre

Spostiamo il nero in più da x al nuovo x (il padre) e togliamo il nero da w per rispettare vincolo 4

WHILE ripristina se è il caso (se il padre era nero) il bilanciamento, altrimenti si termina.

Se si arriva dal caso 1, B è sicuramente rosso, quindi dopo il caso 2 non c’è più bisogno di ribilanciare, perché ora B ha un solo nero (il nero in più) e può essere semplicemente colorato di nero.

caso 3

colore[sinistro[w]] = NEROcolore[w] = ROSSOrotazione-sinistra(T,w)w = destro[padre[x]]

• Il fratello w di x è nero• w ha in questo caso solo il figlo sinistro rosso• cambiamo il colore del sinistro di w e cambiamo quello di w• ruotiamo w col suo figlio sinistroNon violiamo alcun vincolo (3 e 4) e il nuovo fratello si x è ora

nero con figlio sinistro nero, quindi ci portiamo nel caso 4

caso 4

x = root[T ]

c’c’

colore[w] = colore[padre[x]]colore[padre[w]] = NEROcolore[destro[w]] = NEROrotazione-destra(T,padre[x])x = root[T]

• Il fratello w di x è nero• w ha in questo caso solo il figlo destro rosso• cambiamo i colori opportunamente e con una rotazione del

padre di x con w si elimina il nero in più su xNon violiamo alcun vincolo (3 e 4) e abbiamo finito!

Cancellazione in RB: casi

• Abbiamo visto i 4 casi possibili quando il nodo x che sostituisce y (cancellato) è un figlio sinistro

• Esistono anche i 4 casi simmetrici (con destro e sinistro scembiati) quando x è figlio destro

Esercizio: Illustrare i 4 casi simmetrici e scrivere lo pseudo-codice che li gestisce

Cancellazione in RB: algoritmo FixRB-Fix-Cancella(T,x : albero-RB) WHILE x root[T] AND colore[x] = NERO DO IF x = sinistro[padre[x]] THEN w = destro[padre[x]] IF colore[w] = ROSSO THEN colore[padre[x]] = ROSSO colore[w] = NERO

rotazione-destra(T,padre[x]) w = destro[padre[x]] ELSE IF (colore[sinistro[w]] = NERO AND colore[destro[w]] = NERO) THEN colore[w] = ROSSO

x = padre[x] ELSE IF colore[destro[w]] = NERO THEN colore[sinistro[w]] = NERO colore[w] = ROSSO rotazione-sinistra(T,w)

w = destro[padre[x]] colore[w] = colore[padre[x]] colore[padre[w]] = NERO colore[destro[w]] = NERO rotazione-destra(T,padre[x]) x = root[T] ELSE {come il THEN ma con destro e sinistro scambiati} colore[x] = NERO

Cancellazione in RB: algoritmo FixRB-Fix-Cancella(T,x : albero-RB) WHILE x root[T] AND colore[x] = NERO DO IF x = sinistro[padre[x]] THEN w = destro[padre[x]] IF colore[w] = ROSSO THEN colore[padre[x]] = ROSSO colore[w] = NERO

rotazione-destra(T,padre[x]) w = destro[padre[x]] ELSE IF (colore[sinistro[w]] = NERO AND colore[destro[w]] = NERO) THEN colore[w] = ROSSO

x = padre[x] ELSE IF colore[destro[w]] = NERO THEN colore[sinistro[w]] = NERO colore[w] = ROSSO rotazione-sinistra(T,w)

w = destro[padre[x]] colore[w] = colore[padre[x]] colore[padre[w]] = NERO colore[destro[w]] = NERO rotazione-destra(T,padre[x]) x = root[T] ELSE {come il THEN ma con destro e sinistro scambiati} colore[x] = NERO

caso I

caso II

caso III

caso IV

Cancellazoine in RB: esempio

40 55 65Nil Nil Nil

Nil NilNil Nil

Nil Nil Nil Nil

Nil Nil

55 65Nil Nil Nil

NilNil Nil

Nil Nil Nil Nil

Nil 42

Nil Nil

Il colore di x è rossonon si esegue il WHILE

e si colora x di nero

55 65Nil Nil Nil

NilNil Nil

Nil Nil Nil Nil

Nil 42

Nil Nil

Fatto!Il colore di x è rossonon si esegue il WHILE

Cancellazoine in RB: esempio II

55 65Nil Nil Nil

NilNil Nil

Nil Nil Nil Nil

Nil 42

Nil Nil

65Nil Nil Nil Nil

Nil Nil Nil Nil

Nil 42

Nil Nil

Caso IIsimmetrico

65Nil Nil Nil Nil

Nil Nil Nil Nil

Nil 42

Nil Nil

Caso IIsimmetrico

65Nil Nil Nil Nil

Nil Nil Nil Nil

Nil 42

Nil Nil

Il colore di x è ora rossosi esce dal WHILE

65Nil Nil Nil Nil

Nil Nil Nil Nil

Nil 42

Nil Nil

Fatto!

Il colore di x è ora rossosi esce dal WHILE

Cancellazoine in RB: esempio IIIT

NilNil

Nil Nil Nil

Nil Nil NilNil

NilNil

Nil Nil Nil

Nil Nil NilNil

Nil Nil Nil

NilNil

Nil Nil Nil

Nil Nil NilNil

Nil Nil Nil

Caso IIsimmetrico

NilNil

Nil Nil Nil

Nil Nil NilNil

Nil Nil Nil

Caso IIsimmetrico

NilNil

Nil Nil Nil

Nil Nil NilNil

Nil Nil Nil

Caso IIsimmetrico

colore[w] = colore[padre[x]]colore[padre[w]] = NEROcolore[sinistro[w]] = NEROrotazione-sinistra(T,padre[x])x = root[T]

NilNil

Nil Nil Nil

Nil Nil NilNil

Nil Nil Nil

Caso IVsimmetrico

NilNil

Nil Nil Nil

Nil Nil NilNil

Nil Nil Nil

Caso IVsimmetrico

NilNil

Nil Nil Nil

Nil Nil NilNil

Nil Nil Nil

Caso IVsimmetrico

NilNil

Nil Nil Nil

Nil Nil NilNil

Nil Nil Nil

Caso IVsimmetrico

NilNil

Nil Nil Nil

Nil Nil NilNil

Nil Nil Nil

Caso IVsimmetrico

40 55 65

NilNil

Nil Nil Nil

Nil Nil NilNil Nil

Nil Nil

NilNil

Caso IVsimmetrico

40 55 65

NilNil

Nil Nil Nil

Nil Nil NilNil Nil

Nil Nil

NilNil

Fatto!w

Cancellazoine in RB

• L’operazione di cancellazione è concettual-mente complicata!

• Ma efficiente:• il caso 4 è risolutivo e applica 1 sola rotazione• il caso 3 applica una rotazione e passa nel caso 4• il caso 2 non fa rotazioni e passa in uno qualsiasi dei

casi ma salendo lungo il percorso di cancellazione• il caso 1 fa una rotazione e passa in uno degli altri

casi (ma se va nel caso 2, il caso 2 termina)

Quindi

al massimo vengono eseguite 3 rotazioni

Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black.

Documents

Transcript of Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black.

Intrastat e Black List - odcec.torino.it - Black List - Open... · 45/2010/CE; –Risvolti in tema di comunicazioni Intrastat, Black List ed elenco clienti /fornitori –Ripasso regole

Dizionari alberi bilanciati. maggio 2002ASD2002 - Alberi bilanciati2 dizionari ADT che supportano le seguenti operazioni membership anche detta search.

BACK IN BLACK

CARATTERISTICHE TECNICHE - Nolan · 64 65 i 9 black graphite ii 12 metal black i 15 pure white hexagon special i 3 glossy black i 13 flat black i 5 metal white i 14 metal white i

Alberi rosso-neri Le operazioni sugli alberi binari di ricerca hanno complessità proporzionale all’altezza h dell’albero. Gli alberi rosso-neri sono alberi.

BLACK HOLE JAZZ - GSSI

Gli alberi

Esercizio alberi

Museo tra gli Alberi, negli Alberi, sugli Alberi...

esercitazione 16 maggio - Unicamcomputerscience.unicam.it/merelli/algoritmi-complessita/esercitazione6… · Esercitazioni. B-Trees: alberi bilanciati di ricerca progettati per essere

Oidio e black rot - syngenta.it · Chiusura grappolo Invaiatura Trattare in funzione preventiva, ... l’export del vino. Black rot su foglia Black rot su grappolo Oidio e black rot

YOUR ITALIAN BLACK COFFEE

IL VENERDI / BLACK SNOW

alberi conifere

Alberi Patrarchi

Algoritmi e Calcolo Parallelo 2012/2013 - Alberi Red-Black

Black Luigi - Floritelli cucine

SISTEMA NERO “Serie Black”

Copertina :Layout 1 - Abey Australiaassets.abey.com.au/abey_extend/aef_ts/Gessi-BLACK-Goccia... · 2016. 4. 5. · 38025 White 38026 Black 38161 White 38162 Black 38167 White 38168

alberi veneti