2.14 Lezione 14
Sappiamo che, siccome le operazioni di inserimento e rimozione dipendono dall'operazione di ricerca, in quanto devo prima dove inserire o rimuovere un nodo, il caso peggiore anche in questo caso dipende dall'altezza e da come sono inserite le chiavi nell'albero. Il caso peggiore corrisponde quindi ad N.
Possiamo pensare di implementare il delete() in modo lazy, ovvero non rimuoviamo l'elemento dall'albero, ma impostiamo il valore associato alla chiave da rimuovere, a null. Questo ci permette di lasciare la chiave al suo posto, in modo da non dover riordinare i nodi.
Il costo è di 2 ln N' per le operazioni di insert, ricerca, e delete, dove N' è il numero di tutte le coppie chiave-valore che sono state inserite all'interno del BST. OVviamente questo tipo di soluzione non è quella ottimale, sopratutto quando le operazioni di rimozione sono frequenti, in quanto non vado realmente a rimuovere il nodo, consumando memoria.
Per eliminare la chiave più piccola:
- Vado a sinistra finchè non trovo un nodo avente il figlio sinistro == null.
- Rimpiazzo quel nodo con il suo figlio destro (più grande di lui)
- Aggiorno i counts dei sottoalberi.
public void deleteMin(){
root = deleteMin(root);
}
private Node deleteMin(Node x){
if(x.left == null) return x.right; // caso baso che mi fa uscire, ho trovato il nodo più piccolo.
x.left = deleteMin(x.left); // se ha un figlio sinistro continuo la ricorsione
x.count = 1 + size(x.left) + size(x.right); // aggiorno il count
return x;
}Implementazione deleteMin()
Possiamo avere più casi:
-
Caso 0:nel caso in cui devo eliminare un nodo foglia, ovvero privo di sottoalbero sinistro e destro, ci troviamo nel caso più semplice, in quanto l'unica cosa che devo aggiornare è. il parent link a null ed il count. -
Caso 1:Nel caso in cui devo eliminare t, rimpiazzando il parent link. L'unica cosa da fare è aggiornare il link dal nodo padre e collegarlo con l'unico figlio destro o sinistro del nodo da eliminare. Questa operazione preserva l'ordinamento. -
Caso 2:Questo è il caso più difficile, ovvero quando il nodo da rimuovere ha entrambi i figli. In questo caso si va a cercare il successore del nodo t. Il suo successore sarà il minimo nel sottoalbero destro del nodo T.- Cercare il minimo del sottoalbero, significa andare prima a destra, e poi a sinistra finchè non trovo un nodo senza figlio sinistro. Facciamo questa operazione perchè dobbiamo sostituire al nodo T un nodo che sia il minimo del sottoalbero destro, in modo da poterlo sostituire a T. Questa operazione ci darà come risultato che avremo al posto di T un nodo avente tutti nodi più piccoli alla sua sinistra e tutti nodi più grandi alla sua destra.
public void delete(Key key){
root = delete(root, key);
}
private Node delete(Node x, Key key){
// se il nodo curr è null ritorno null. Questo caso comprende anche il caso in cui il nodo non ha figli
if(x == null) return null;
int cmp = key.compareTo(x.key);
// cerco il nodo
if(cmp < 0) x.left = delete(x.left, key);
else if(cmp > 0) x.right = delete(x.right, key);
//una volta trovato...
else{
// se ha solo un figlio ritorno quello non nullo
if(x.right == null) return x.left;
if(x.left == null) return x.right;
// ultimo caso: quando il nodo ha entrambi i figli:
Node t = x; // salvo il nodo corrente
x = min(t.right); // cerco il minimo nel sottoalbero destro del nodo corrente e lo salvo in x (curr)
x.right = deleteMin(t.right); // elimino il minimo e lo imposto come root del sottoalbero destro di curr
x.left = t.left; // collego il nodo sinsitro
}
x.count = size(x.left) + size(x.right) + 1; //aggiorno il count
return x;
}Questa soluzione è ancora insoddisfacente, in quanto se gli alberi non sono random possiamo avere una complessità proporzionale a sqrt(N) per le operazioni di eliminazione. Ancora non è stata trovata un'implementazione semplice ed efficace per la delete() dei BST.
Se mantengo l'albero perfettamente bilanciato, l'operazione di delete sarà comparabile con le operazioni di search() ed insert().
Ancora una volta, le operazioni che dipendono dalla search(), ereditano il tempo di esecuzione, infatti:
| Implementazione ST | search | Insert | delete |
|---|---|---|---|
| Ricerca sequenziale (lista non ordinata) | N | N | N |
| Ricerca sequenziale (lista ordinata) | log N | N | N |
| BST | N | N | N |
Tempo garantito
| Implementazione ST | search hit | Insert | delete |
|---|---|---|---|
| Ricerca sequenziale (lista non ordinata) | N / 2 | N | 1/2 N |
| Ricerca sequenziale (lista ordinata) | Log N | N / 2 | 1/2 N |
| BST | 1.39 lg N | 1.39 lg N | sqrt(N) |
Average case
Per avere una complessità logaritmica in un BST dobbiamo mantenere l'albero perfettamente bilanciato, cioè la distanza tra la radice e le foglie, deve essere uguale per tutte le foglie. Per garantire questa complessità possiamo pensare ad un albero 2-3.
In un albero 2-3 possiamo avere nodi di tipo 2 che contengono una chiave e due figli. Possiamo inoltre avere nodi di tipo 3, che contengono due chiavi sempre in ordine crescente, e tre link ai nodi figli:
Il sottoalbero a sinistra ha tutte le chiavi che sono più piccole della prima chiave (k1), il nodo centrale contiene tutte le chiavi comprese tra k1 e k2, mentre il nodo destro contiene tutte le chiavi che sono più grandi di k2. Ovviamente, questo tipo di albero è ordinato, e perfettamente bilanciato.
La sfida consiste nel mantenere, nelle varie operazioni che cambiano la struttura dell'albero, il bilanciamento perfetto. Ovviamente i nodi dell'albero sono ordinati per favorire le operazioni di ricerca in quanto le altre operazioni dipendono dalla ricerca.
- Confronto la chiave da cercare con la chiave nel nodo corrente
- trovo un intervallo che contenga quella chiave
- seguo il collegamento associato in modo ricorsivo
Primo caso: Aggiungere una chiave in un nodo di tipo 2 per creare un nodo di tipo 3.
- partiamo con l'operazione di ricerca dalla radice.
- Quando troviamo un nodo foglia, ovvero con figli == null, possiamo inserire la chiave all'interno del nodo di tipo 2, e quindi trasformarlo in un nodo di tipo 3.
In questo modo non abbiamo aumentato l'altezza dell'albero, ma abbiamo solo trasformato un nodo.
Secondo caso: Aggiungere una chiave in un nodo di tipo 3
- Partiamo con l'operazione di ricerca
- Appena troviamo un nodo foglia ci fermiamo.
- Siccome non vogliamo aumentare l'altezza dell'albero inserendo un altro nodo, creiamo un nodo di tipo 4 temporaneo.
- A questo punto posso far salire la chiave centrale al livello superiore, mantenendo l'ordinamento dell'albero.
- Di conseguenza il nodo precedente di tipo 2 diventerà di tipo 3.
Questa operazione si propaga verso l'alto fino alla radice, ad esempio:
Se abbiamo già tutti nodi di tipo 3, l'operazione si propagherà fino alla radice, che diventerà a sua volta di tipo 4 temporaneo. Questo nodo, verrà diviso in due nodi due.
- Inserisco il primo nodo
- Inserisco il secondo nodo, creando un nodo di tipo 3.
- All'inserimento del terzo nodo avremo un nodo 4 temporaneo. Siccome siamo nella radice, deve essere diviso in due nodi di tipo 2, facendo crescere di 1 l'altezza dell'albero.
- Continuo in questo modo creando nodi di tipo 2, 3 e dividendo in due nodi 2 quando abbiamo nodi di tipo 4 temporaneo.
Dal momento in cui non abbiamo una rappresentazione specifica del link nella vecchia rappresentazione, e dato che ogni nodo è puntato da un link che parte dal genitore, possiamo rappresentare il colore del link all'inerno dei nodi.
<<<<<<< HEAD
Siamo interessati al caso peggiore, in quanto vogliamo garantire un tempo di completamento delle operazioni al più lograitmico. Già dai BST sappiamo che le prestazioni sono correlate all'altezza dell'albero.
Se abbiamo tutti nodi di tipo 2, chiaramente l'altezza dell'albero, a parità di N, sarà maggiore. Se invece abbiamo tutti nodi di tipo 3 l'altezza sarà minore.
-
Caso peggiore:lg N (tutti nodi di tipo 2) -
Caso migliore:log3 N (tutti nodi di tipo 3) circa .631 lg N
Dal momento in cui il caso peggiore garantisce un'altezza logaritmica, va a garantire un tempo di completamento logaritmico per le operazioni derivanti dalla search().
Il bilanciamento perfetto ci permette di garantire prestazioni di questo tipo. Delle ricerche ci permettono di affermare che avremo un'altezza tra 12 e 20 per alberi di milioni di nodi e tra 18 e 30 per alberi di miliardi di nodi.
| Implementazione ST | search | Insert | delete |
|---|---|---|---|
| Ricerca sequenziale (lista non ordinata) | N | N | N |
| Ricerca sequenziale (lista ordinata) | log N | N | N |
| BST | N | N | N |
| 2-3 tree | c lg N | c lg N | c lg N |
Tempo garantito
| Implementazione ST | search hit | Insert | delete |
|---|---|---|---|
| Ricerca sequenziale (lista non ordinata) | N / 2 | N | 1/2 N |
| Ricerca sequenziale (lista ordinata) | Log N | N / 2 | 1/2 N |
| BST | 1.39 lg N | 1.39 lg N | sqrt(N) |
| 2-3 tree | c lg N | c lg N | c lg N |
Average case
La diretta implementazione degli alberi 2-3 è molto complicata, e non priva di problemi.
Diventa complicato gestire diversi tipi di nodi, in quanto i nodi 2 e 3 hanno caratteristiche diverse, inoltre abbiamo bisogno di un numero maggiore di confronti per muoversi lungo l'albero, ecc.
public void put(Key key, Value val){
Node x = root;
while(x.getTheCorrectChild(key) != null){
x = x.getTheCorrectChildKey();
if(x.is4Node()) x.split();
}
if(x.is2Node()) x.make3Node(key, val);
else if(x.is3Node()) x.make4Node(key, val);
}Codice di fantasia
Abbiamo quindi capito che ci è molto difficile implementare questo tipo di albero, dobbiamo quindi trovare una strada più semplice.
La sfida fondamentale consiste nel rappresentare i nodi 3, usando nodi 2. Usando un BST standard non abbiamo modo di distinguere un nodo 2 da un nodo 3, quindi non possiamo ricostruire il mapping di un albero 2-3 da un BST.
Potremmo usare un BST ordinario, ma come già detto non potremmo distinguere i nodi 2 dai 3.
Potremmo pensare di inserire dei nodi di collegamento, per tenere traccia dei nodi di tipo 3, ma questo approccio richiederebbe molto spazio e codice difficile da implementare.
Consiste nell'usare dei link rossi. Questo approccio è molto usato nella pratica, e come restrizione arbitraria permettiamo che i link rossi possano comparire solo a sinistra, mai a destra. In pratica, attraverso questo workaround possiamo rappresentare un albero 2-3 attraverso un BST.
Usiamo quindi i link rossi per raprresentare un nodo 2-3, In questo modo diventa semplice mantenere un mapping 1-1 su un albero 2-3.
Un modo analogo di procedere, è quello di considerare i BST - red-black come normali BST, che soddisfano le proprietà:
- Nessun nodo ha due link rossi connessi ad esso.
- Ogni cammino dalla radice ad una foglia contiene lo stesso numero di collegamenti neri.
- I collegamenti rossi sono solo a sinistra.
Possiamo dimostrare quindi che esiste una corrispondenza 1-1 tra gli alberi 2-3 ed i BST semplicemente considerando i link rossi come se fossero orizzontali:
Con questa definizione, l'operazione di ricerca è la stessa per i BST, non abbiamo bisogno di modifiche, in quanto non abbiamo bisogno di sapere il colore del link. Anche altre operazioni, come la Iterazione e la selezione sono identiche.
public Val get(Key key){
Node x = root;
while(x!=null){
int cmp = key.compareTo(x.key);
if(cmp < 0) x = x.left;
else if(cmp > 0) x = x.right;
else return x.val;
}
return null;
}======= Aggiungiamo quindi una variabile booleana che rappresenta proprio il colore del nodo, true per rosso e false per nero. Abbiamo inoltre un metodo isRed() per sapere se il dato nodo è rosso o nero.
45ef20137313cde4d78d8f44e716b5c3ebb42166
Abbiamo detto che le operazioni che sono impattate dalla rappresentazione dei link, rispetto ai BST standard, sono quelle che modificano la struttura dell'albero, una di queste è sicuramente l'inserimento.
Durante l'operazione di inserimento, è necessario mantenere l'ordine simmetrico delle chiavi, come nei BST, ed il bilanciamento nero perfetto. Questo bilanciamento ci dice che il numero di archi neri che collegano la radice alle foglie siano in numero costante, per tutti i nodi.
Quello che non manteniamo invariato sono i colori dei link. Infatti, durante le operazioni di inserimento possono verificarsi vari casi:
- Il link rosso compare a destra
- Un dato nodo ha due nodi figli che sono entrambi rossi (nodo 4 temporaneo)
- Un dato nodo ha sia il padre che il figlio rossi (nodo 4 temporaneo)
- Un dato nodo ha il padre rosso ed il figlio destro rosso (nodo 4 temporaneo)
Possiamo risolvere queste problematiche con delle semplici operazioni degli alberi R-N:
- Rotazione a destra
- Rotazione a sinistra
- Inversione di colore
Queste operazioni sono le uniche che servono per mantenere le proprietà di simmetria e di bilanciamento nero perfetto.
Nel caso in cui ho un link rosso con un figlio destro, devo portare questo link rosso a sinistra. Per fare questo effettuo una rotazione.
- Vado a chiamare x il nodo destro del nodo h.
- Vado a stabilire come figlio destro di h, il figlio sinistro del nodo x.
Quello che accade nella pratica è il seguente:
- Aggiungo un link tra h e il figlio sinistro di x
- Collego il figlio sinistro di x come figlio destro di h
- Il figlio sinistro di x sarà proprio h
- Il colore di x sarà uguale al colore di h
- Il colore di h diventerà rosso.
- Ritorno x.
private Node rotateLeft(Node h){
assert isRed(h.right);
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = RED;
return x;
}Codice per la rotazione a sinistra
private Node rotateRight(Node h){
assert isRed(h.left);
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = RED;
return x;
}Codice per la rotazione a destra
Il color flip si ha quando abbiamo due figli dello stesso nodo di colore rosso.
In questo caso non devo fare altro che colorare entrambi i figli di nero, e colorare di rosso il nodo genitore.
private void flipColors(Node h){
assert !isRed(h);
assert isRed(h.left);
assert isRed(h.right);
h.color = RED;
h.left.color = BLACK;
h.right.color = BLACK;
}Devo inserire un nodo in un albero che ha esattamente un nodo, ovvero la radice.
Ovviammente confronto la chiave che devo inserire con il nodo già presente.
Se la chiave da inserire è minore della chiave già presente, la inserisco a sinistra; ovviamente non violiamo alcun ordine siccome il link rosso si trova a sinistra.
Se la chiave invece è maggiore del nodo, inevitabilmente il link rosso si troverà a destra, e questa è una cosa non consentita, in quanto i link rossi possono trovarsi solo a destra. Per risolvere questo problema effettuiamo una left rotation, ottenendo sia un albero ordinato sia che non viola alcuna restrizione.
- Effettuiamo una insert standard dei BST, coloriamo il nuovo link di rosso.
- Se il nuovo link rosso è un link destro, ruotiamo a sinistra.
Mi trovo in un albero di questa forma:
B / A
Ottengo quindi
B
/
A C
Con due link rossi. Avendo un padre con due figli entrambi rossi, dobbiamo effettuare un color Flip. Così facendo i link ai figli diventano neri, mentre essendo il padre la root, il nuovo link rosso viene perduto, aumentando così di uno l'altezza di tutto l'albero.
Mi trovo in questa situazione:
C / B
Ottengo quindi:
C / B / A
Entrambi i nodi A e B sono rossi, quindi effettuo prima una rotazione, portandomi in questo stato:
B
/ \
A C
Dove ancora una volta entrambi i nodi A e C sono rossi, di conseguenza effettuo un color flip.
Mi trovo in questa situazione:
C
/
A
Dove il nodo A è di tipo rosso. Devo inserire B, quindi mi ritrovo nello stato:
C
/
A
\
B
Dove ancora una volta i link A e B sono rossi.
Effettuo quindi una rotazione a sinistra:
C
/
B
/
A
Dove ancora una volta sia B che A sono rossi. Effettuo un'ulteriore rotazione a destra:
B
/ \
A C
Dove ancora una volta sia A che C sono rossi. Effettuo finalmente un Color Flip.
Importante: Notiamo quindi che non importa l'ordine con cui inseriamo le chiavi, alla fine dell'esecuzione dell'algoritmo avremo sempre la stessa disposizioni delle chiavi per ogni sequenza di inserimento.
private Node put(Node h, Key key, Value val){
if(h == null) return new Node(key, val, RED);
int cmp = key.compareTo(h.key);
if(cmp < 0)
h.left = put(h.left, key, val);
else if(cmp > 0) h.right = put(h.right, key, val);
else h.val = val;
if(isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
if(isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
if(isRed(h.left) && isRed(h.right)) flipColors();
return h;
}- Se ho un figlio destro rosso ed un figlio sinistro, allora devo fare la rotazione a sinsitra.
- Se ho che sia il figlio sinistro che il figlio sinistro del figlio, sono rossi, devo fare una rotazione a destra.
- Quando entrambi i figli sinistro e destro sono rossi, allora devo effettuare un color flip.
Quello che ci fa mantenere l'ordinamento dell'albero è il fatto che non importa l'ordine con cui inserisco le chiavi, quindi la configurazione sarà sempre la stessa a prescindere da quello che sarà l'ordine di inserimento.