Alberi Binari di Ricerca e Alberi Rosso-Neri

03/02/2008
Obiettivi
ƒ Studiare strutture dati che consentano di
effettuare in modo efficiente le operazioni di
Alberi Binari di Ricerca
e
Alberi Rosso-Neri
•Minimo e massimo
•Successore
•Inserimento e cancellazione
•Ricerca
Ricerca
ƒ Studieremo due tipi di strutture dati
•Alberi binari di ricerca
•Alberi rosso-neri
Alberi binari di ricerca
„
„
Binary Search Property
Alberi binari
Ciascun nodo x è costituito da 4 campi
„
• key[x] (chiave)
• left[x] (puntatore al figlio sinistro)
• right[x] (puntatore al figlio destro)
• p[x] (puntatore al padre)
Sia x un nodo dell’albero binario di ricerca.
• key[y] ≤ key[x] per ogni nodo y nel sottoalbero
sinistro di x
• key[y] ≥ key[x] per ogni nodo y nel sottoalbero
destro di x
• I sottoalberi sinistro e destro di x sono ancora
alberi binari di ricerca
5
3
2
Visita Inorder
„
„
7
5
8
Minimo e Massimo
Algoritmo ricorsivo che stampa la sequenza
ordinata delle chiavi nell’albero
Tempo proporzionale al numero di nodi
„
„
5
Inorder-Tree-Walk(x)
If x ≠ NIL
then Inorder-Tree-Walk(left[x])
2
print key[x]
Inorder-Tree-Walk(right[x])
3
7
5
8
Stampa la sequenza 2-3-5-5-7-8
Il minimo è la foglia più a sx, il massimo quella più a dx
Tempo proporzionale all’altezza dell’albero
Tree-Minimum(x)
while left[x]
[ ] ≠ NIL
do x ← left[x]
return x
5
3
2
Tree-Maximum(x)
while right[x]
g [ ] ≠ NIL
do x ← right[x]
return x
7
5
8
1
03/02/2008
Successore di un nodo
„
E’ il nodo con chiave minima nel sottoalbero dx del nodo
‰
„
Ricerca
Se il nodo non ha figlio dx risaliamo alla ricerca di un nodo figlio sx
di qualcuno. Il successore è quel “qualcuno”
Tempo proporzionale all’altezza dell’albero
„
„
Tree-Successor(x)
g [ ] ≠ NIL
if right[x]
then return Tree-Minimum(right[x])
y ← p[x]
while y≠NIL and x=right[y]
do x←y
y←p[y]
return y
Confronta il valore k da cercare con la chiave di ogni
nodo
Tempo proporzionale all’altezza dell’albero
Tree-Search(x,k)
if x=NIL
NIL or kk=key[x]
k [ ]
then return x
if k < key[x]
then return Tree-Search(left[x],k)
else return Tree-Search(right[x],k)
Il successore di 15 è 17; il successore di 13 è 15
Per cercare 13 seguiamo il path 15Æ6Æ7Æ13
Inserimento
„
„
Segue un cammino discendente dalla radice a una foglia
per inserire un nodo
Tempo proporzionale all’altezza dell’albero
Tree-Insert(T,z)
y ← NIL
x ← root[T]
while x≠NIL
do y ← x
if key[z]<key[x]
then x ←left[x]
else x←right[x]
p[z]←y
If y=NIL
then root[T]←z
else if key[z]<key[y]
then left[y]←z
else right[y]←z
Cancellazione
„
L’algoritmo distingue tre casi riguardo al nodo
da cancellare
‰
È una foglia
„
‰
„
‰
Collega il figlio col padre del nodo cancellato
Ha due figli
„
„
Cancella il nodo e aggiorna p[x]
Ha un solo figlio
Cerca il successore e lo scambia col nodo da cancellare
Tempo proporzionale all’altezza dell’albero
Inserimento del nodo 13
Tree-Delete(T,z)
if left[z]=NIL or right[z]=NIL
42
then y Å z
else y Å Tree-Successor(z)
32
if left[y] ≠ NIL
then x Å left[y]
else x Å right[y]
26
if x ≠ NIL
then p[x] Å p[y]
Il nodo 51 è una foglia
if p[y]=NIL
then root[T] Å x
else if y = left[p[y]]
then left[p[y]] Å x
42
else right[p[y]] Å x
if y ≠ z
then key[z] Å key[y]
32
“ copy other fields ”
return y
26
Cancellazione
65
73
65
42
51
32
65
73
51
42
Il nodo 32 ha un
solo figlio
26
73
51
26
65
65
42
73
32
26
73
42
73
51
Il nodo 65
ha due figli
73 è il successore
di 65
32
26
2
03/02/2008
Alberi binari di ricerca
„
„
Alberi Rosso-Neri (Red-Black)
Le operazioni esaminate possono essere effettuate in
tempo proporzionale all’altezza dell’albero
Dato un insieme di chiavi, possiamo avere più alberi
binari di ricerca con altezze diverse
‰
ƒ Sono alberi binari di ricerca estesi
ƒ Ciascun nodo contiene un campo addizionale
che riporta il suo colore
anche uno totalmente sbilanciato (se la sequenza è ordinata)
2
5
3
3
5
7
ƒ L
Le operazioni
i i di inserimento
i
i
t e cancellazione
ll i
vengono opportunamente integrate in modo
tale da rendere l’albero bilanciato
5
2
5
8
7
8
Un esempio di albero Rosso-Nero
La caratterizzazione degli alberi Rosso-Neri
avviene attraverso la formulazione di
quattro proprietà vincolanti
65
42
32
26
73
51
Caratterizzazione
NIL NIL
NIL NIL NIL
NIL NIL
Proprietà n. 1
Proprietà n. 2
Ogni nodo dell’albero è rosso o nero
Ogni foglia dell’albero (NIL) è nera
46
52
26
62
45
21
31
51
NIL
85
NIL
NIL
3
03/02/2008
Proprietà n.3
Proprietà n.4
Se un nodo è rosso entrambi i suoi figli
sono neri
Dato un nodo, ogni percorso discendente
verso le foglie contiene lo stesso numero di
nodi neri
65
42
42
32
12
26
78
73
51
NIL NIL
NIL NIL NIL
NIL NIL
Proprietà
Altezza-nera (Black-height)
1. Ogni nodo è rosso o nero
ƒ Altezza-nera di un nodo x (bh(x)):
il numero di nodi neri lungo un qualsiasi cammino
discendente da x verso una foglia, senza contare il nodo
di partenza
2. Ogni foglia (NIL) è nera
3. Se un nodo è rosso entrambi i suoi figli
sono neri
ƒ L’altezza
L’ l
nera d
delle
ll ffoglie
li è zero
ƒ Altezza-nera di un albero Rosso-Nero T (bh(T)):
4. Dato un nodo, ogni percorso discendente
verso le foglie contiene lo stesso numero di
nodi neri
altezza-nera della sua radice
Altezza-nera (Black-height)
Lemma 1
bh(32) = 1
42
bh(42) = 2
bh(73) =1
bh(T) = bh(65) = 2
Un albero Rosso-Nero con n nodi interni ha
altezza al più 2·lg(n+1)
65
32
26
NIL
73
51
NIL NIL NIL
NIL
NIL
NIL
Lemma 2
Dato un nodo x appartenente ad un albero
Rosso-Nero, il sottoalbero ivi radicato
contiene almeno 2bh(x)-1 nodi interni
4
03/02/2008
Dimostrazione Lemma 2
Dimostrazione Lemma 2
Dimostriamo il Lemma 2 per induzione sull’altezza nera bh(x)
del nodo x.
x
Ipotesi induttiva: sia vero per un nodo con altezza nera bh(x)-1
Passo induttivo: Consideriamo un nodo x con altezza nera bh(x)
e due figli…
Ciascuno dei due figli di x avrà altezza nera bh(x)
oppure bh(x)-1, a seconda del suo colore.
Base: bh(x) = 0
x
Se bh(x)=0, allora x è una foglia. Pertanto, il
sottoalbero radicato in x ha 20-1=0 nodi interni.
bh(x)-1
bh(x)
6
2
6
8
2
bh(x)
8
Dimostrazione Lemma 2
Dimostrazione Lemma 1
Dato che l’altezza nera dei figli di x è minore o uguale
all’altezza nera di x, per l’ipotesi induttiva ciascun figlio
ha almeno 2bh(x)-1-1 nodi interni.
Un albero Rosso-Nero con n nodi interni ha
altezza al più 2· lg(n+1)
Quindi, il sottoalbero radicato in x ha almeno
(2bh(x)-1-1)
1) + (2bh(x)-1-1)
1) + 1 nodi interni
Dim.
Sia bh(T) l’altezza nera dell’albero.
Dal Lemma 2,, il numero n di nodi interni è tale che
n≥ 2bh(T) –1
(2bh(x)-1-1) + (2bh(x)-1-1) + 1 =
2bh(x)-1 + 2bh(x)-1 –1
=
2*2bh(x)-1 – 1
= 2bh(x) –1
Dimostrazione Lemma 1
Pertanto
Sia h l’altezza dell’albero.
La proprietà 3. impone che almeno la metà dei nodi che
separano la radice dalle foglie siano neri (ci sono più nodi
neri che rossi).
Quindi, bh(T) ≥ h/2.
Operazioni
„
n ≥ 2h/2 -1
n +1 ≥ 2h/2
„
‰
log(n+1) ≥ h/2
h ≤ 2lg(n+1)
Un albero Rosso-Nero con n nodi interni
ha altezza h=O(lg n)
Un albero Rosso-Nero con n nodi interni ha
altezza h=O(lg n)
Quindi le seguenti operazioni possono essere
effettuate in tempo logaritmico (efficiente!)
‰
‰
„
Ricerca
Minimo e massimo
Successore
Cosa accade per inserimento e
cancellazione?
5
03/02/2008
Operazioni
„
„
„
Rotazioni
ƒ Operazioni che comportano solo uno spostamento di
puntatori
ƒ Effettuate in tempo costante
ƒ Non cambiano la struttura dei sottoalberi del nodo “perno”
ƒ La visita inorder resta la stessa
Le operazioni di inserimento e cancellazione
mutano la struttura dell’albero
Le proprietà dei colori potrebbero non essere
più rispettate
E’ necessaria l’introduzione di una ulteriore
operazione per ripristinare tali proprietà
‰
‰
Right Rotate(T y)
Right-Rotate(T,y)
x
y
Rotazione dx
Rotazione sx
a
x
a
y
c
Left-Rotate(T,x)
b
b
c
Stessa visita inorder: a-x-b-y-c
z
Left-Rotate(T,x)
y
x
yÅright[x]
a
right[x]Å left[y]
If left[y] ≠ NIL
then p[left[y]] Å x
p[y]Åp[x]
If p[x] = NIL
then root[T] Å y
else if x = left[p[x]]
then left[p[x]] Å y
else right[p[x]] Å y
left[y] Å x
p[x] Å y
Algoritmo di Inserimento di un nodo
z
x
y
b
c
a
c
b
ƒ Verifica se l’albero risultante viola le proprietà degli alberi
Rosso-Neri
Rosso
Neri (es: due nodi rossi consecutivi)
ƒ In caso di violazione, si risale l’albero sino alla radice
operando opportunamente rotazioni e cambiamenti di
colore
ƒPrevede tre possibili casi di intervento, più altri tre simmetrici
RB-Insert(T,x)
Tree-Insert(T,x)
color[x]Å RED
//Violazione: x e p[x] sono rossi
While x ≠ root[T] and color[p[x]] = RED
do if p[x] = left[p[p[x]]]
then y Å right[p[p[x]]]
if color[y] = RED
then color[p[x]] = BLACK
color[y] = BLACK
Caso 1
color[p[p[x]]] = RED
x Åp[p[x]]
else if x = right[p[x]]
then x Å p[x]
Left-Rotate(T,x)
color[p[x]] = BLACK
color[p[p[x]]] = RED
Right-Rotate(T,p[p[x]])
ƒ Inserisce il nuovo nodo (rosso) nell’albero mediante
l’algoritmo di inserimento per alberi binari di ricerca
Caso 2
Caso 1
if p[x] = left[p[p[x]]]
//Se p[x] è figlio sx di suo padre
then y Åright[p[p[x]]]
//Se y, lo zio di x, è rosso
if color[y] = RED
then color[p[x]] = BLACK
color[y] = BLACK
[p[p[ ]]] = RED
color[p[p[x]]]
x Åp[p[x]]
x
p[p[x]]
Caso 3
p[x]
y
else
… (right case)
color[root[T]] Å BLACK
x
6
03/02/2008
Caso 1
„
Caso 2
Il nodo x è risalito di 2 livelli
‰
‰
//Se y, lo zio di x, è nero
//Se x è figlio dx di suo padre
else if x = right[p[x]]
then x Å p[x]
Left-Rotate(T,x)
Se p[x] è rosso, restiamo nel ciclo while
Se p[x] è nero o è la radice usciamo dal while e coloriamo
di nero la radice
„
Questo caso può essere eseguito al max lg n volte
„
Ogni volta impiega tempo O(1)
p[p[x]]
p[x]
y
x
x
Caso 2
„
„
„
„
x
Caso 3
Si verifica in uscita al caso 2: x è figlio sx di suo padre
Il nodo x non sale di livello
Lo scopo è fare in modo che x diventi figlio sx di suo
padre
Questo caso può verificarsi una sola volta perché
porta al caso 3
Viene eseguito in tempo O(1)
color[p[x]] = BLACK
color[p[p[x]]] = RED
Right-Rotate(T,p[p[x]])
p[p[x]]
p[x]
x
Caso 3
„
„
„
„
Questo caso si verifica in uscita al caso 2
E’ un caso terminale: x è rosso e p[x] è nero (la
violazione è stata eliminata)
Si esce dal while e si colora di nero la radice
dell’albero
Viene eseguito in tempo O(1)
p[x]
p[p[x]]
y
p[x]
y
x
x
y
In definitiva
„
La complessità della procedura di
inserimento è data dalla somma delle
complessità nei tre casi, quindi è O(lg n)
7
03/02/2008
Un esempio 1/4
Un esempio 2/4
Inseriamo nell’albero il nodo con chiave 4
Caso 1: x è figlio sx di suo padre e y è rosso
11
2
14
1
7
5
NIL NIL
11
11
NIL
2
15
NIL
8
7
5
NIL NIL
violazione
NIL NIL NIL NIL
4
x
y
NIL
8
1
NIL
4
x
2
14
x
1
NIL
8
7
NIL NIL
NIL NIL NIL
5
4
15
NIL
NIL
NIL NIL
NIL
8
NIL
NIL NIL NIL
NIL NIL
Un esempio 4/4
Caso 2: x è figlio dx di suo padre e y è nero
p[p[x]]
Caso 3: x è figlio sx di suo padre e y è nero
14
p[x]
y
7
11
p[p[x]]
11
y
2
11
y
p[x]
15
NIL
y
5
NIL NIL
NIL NIL NIL
Un esempio 3/4
p[x]
7
p[x]
NIL NIL
11
14
p[p[x]]
15
NIL
p[x]
NIL
2
14
1
p[p[x]]
14
p[x]
p[x]
7
y
7
14
2
x
y
11
x
1
7
NIL
15
x
x
2
NIL NIL
5
8
NIL
NIL
NIL
1
4
8
5
NIL
NIL
2
15
NIL
NIL
1
8
5
NIL
NIL
NIL
15
NIL NIL
1
8
5
NIL NIL
4
14
NIL NIL NIL NIL
15
NIL NIL NIL
NIL
NIL
NIL NIL
NIL
4
NIL
NIL
NIL NIL
NIL
4
NIL
NIL
NIL
NIL
NIL NIL
Albero bilanciato
Algoritmo di Cancellazione di un nodo
Algoritmo di Cancellazione di un nodo
ƒ Cancella il nodo dall’albero mediante l’algoritmo di
cancellazione per alberi binari di ricerca
ƒ Se il nodo cancellato è nero, i nodi nel sottoalbero
radicato nel nodo cancellato non rispettano la proprietà 4.
ƒ Verifica se l’albero risultante viola le proprietà degli
alberi Rosso-Neri
ƒSe il nodo cancellato è rosso tutto OK
ƒSe il nodo cancellato è nero potrebbero esserci violazioni
ƒ Idea: affidiamo al nodo x, figlio del nodo rimosso, un colore
nero extra da smaltire appena possibile
ƒ In caso di violazione, si risale l’albero sino alla radice
operando opportunamente rotazioni e cambiamenti di
colore
ƒ Scopo: risalire da x alla radice alla ricerca di un nodo rosso
su cui “scaricare” il colore nero extra
ƒSe un nodo rosso non viene trovato, scarichiamo il nero
extra sulla radice
ƒPrevede quattro possibili casi di intervento, più altri quattro simmetrici
8
03/02/2008
RB-Delete-fixup(T,x)
While x ≠ root[T] and color[x] = black
do if x=left[p[x]]
then w Å right[p[x]]
if color[w] = red
then color[w] Åblack
color[p[x]] Å red
Caso 1
Left-Rotate[T,p[x]]
w Å right[p[x]]
if color[left[w]]=black and color[right[w]]=black
then color[w] Å red
Caso 2
x Å p[x]
else if color[right[w]]=black
then color[left[w]] Å black
color[w] Å red
Caso 3
Right-Rotate(T,x)
w Å right[p[x]]
color[w] Å color[p[x]]
color[p[x]] Å black
Caso 4
color[right[w]] Å black
Caso 1
p[x]
x
p[x]
w
„
„
„
„
„
Dopo la trasformazione non ci sono due rossi
consecutivi
Il numero di nodi neri dalla radice alle foglie è lo
stesso di prima, avendo x un colore nero in più
Il nodo x è sceso di un livello
Il nodo w, fratello di x, è nero: si esce dal caso 1 e si
entra in uno dei casi 2,3, o 4 (w nero)
Viene eseguito in tempo O(1)
Caso 2
„
Il nuovo nodo x può essere sia rosso che nero
‰
‰
„
„
„
Se è rosso si esce dal while e si colora x di nero (caso
terminale)
Se è nero si resta nel while
I sottoalberi radicati nei figli di x hanno un nodo nero
in più (colore extra di x) e uno in meno (w ora è
rosso): stesso numero di nodi neri
Il nodo x è salito di un livello
Questo caso può ripetersi un numero di volte
proporzionale all’altezza dell’albero, se p[x] è nero
x
p[x]
w
x
Left-Rotate(T,p[x])
x Å root[T]
else (… right case)
color[x] Åblack
Caso 1
//Se x è figlio sx di suo padre
//Se w, fratello di x, è rosso
if color[w] = red
then color[w] Åblack
color[p[x]] Å red
Left-Rotate[T,p[x]]
w Å right[p[x]]
w
… conduce ad uno dei casi 2,3, o 4 …
Caso 2
//Se w, fratello di x, è nero e ha due figli neri
if color[left[w]]=black and color[right[w]]=black
then color[w] Å red
x Å p[x]
p[x]
x
x
p[x]
w
w
x
Caso 3
//Se w, fratello di x, è nero e ha il figlio dx nero e il sx rosso
else if color[right[w]]=black
then color[left[w]] Å black
color[w] Å red
Right-Rotate(T,w)
w Å right[p[x]]
p[x]
p[x]
x
w
x
p[x]
w
x
w
9
03/02/2008
Caso 3
„
„
„
„
Caso 4
Dopo la trasformazione non ci sono due nodi rossi
consecutivi
Il nodo x resta allo stesso livello
Questo caso porta al caso 4
Viene eseguito
g
in tempo
p O(1)
( )
//Se w, fratello di x, è nero e ha il figlio dx rosso
color[w] Å color[p[x]]
color[p[x]] Å black
color[right[w]] Å black
Left-Rotate(T,p[x])
x Å root[T]
w
p[x]
x
p[x]
w
x
p[x]
w
x
Caso 4
„
„
„
E’ un caso terminale
Ora x punta alla radice dell’albero, sulla quale viene
scaricato il nero extra
Viene eseguito in tempo O(1)
In definitiva
„
La complessità della procedura di
cancellazione è data dalla somma delle
complessità nei tre casi, quindi è O(lg n)
Strutture dati animate con JIVE
ƒ Al link http://jive.dia.unisa.it/asd è disponibile un
software scritto in Java che consente di
ƒ Creare alberi binari di ricerca e alberi Rosso-Neri
ƒ Effettuare operazioni di inserimento e cancellazione
10