ALBERI AVL: INSERIMENTO E CANCELLAZIONE ALBERI ROSSO NERI DYNAMIC SELECT ALGORITMI E STRUTTURE DATI

(1)

ALGORITMI E STRUTTURE DATI

ALBERI AVL: INSERIMENTO E CANCELLAZIONE ALBERI ROSSO NERI

DYNAMIC SELECT

(2)

ALBERI AVL

INSERIMENTO E CANCELLAZIONE

(3)

ALBERI AVL

INSERIMENTO E CANCELLAZIONE

▸ L’inserimento può violare la proprietà AVL su più nodi nel percorso che va dalla radice al punto dove è stato inserito il nuovo nodo

(4)

ALBERI AVL

INSERIMENTO E CANCELLAZIONE

▸ La cancellazione analogamente può violare la proprietà AVL nei nodi antenati del nodo cancellato

(5)

ALBERI AVL

INSERIMENTO E CANCELLAZIONE

▸ La cancellazione analogamente può violare la proprietà AVL nei nodi antenati del nodo cancellato

▸ Vediamo come ogni sbilanciamento può essere risolto tramite una sequenza di rotazioni

(6)

ALBERI AVL

RIBILANCIAMENTO

Se emerge uno sbilanciamento dopo un inserimento o una cancellazione di un nodo, allora il fattore di sbilanciamento sarà 2 o -2, e causato da un nodo in più (o in meno) in uno dei 4 sottoalberi T0 T1 T2 T3.

X Y

Z

T₁

T₀ T₂ T₃

SS SD DS DD

In funzione di dove emerge lo sbilanciamento, definiremo una sequenza di rotazioni opportuna che ribilanci l’albero.

Per simmetria, tratteremo solo due dei 4 casi, ovvero SS e SD.

(7)

ALBERI AVL

RIBILANCIAMENTO - CASO SS

X

Y

T₁ T₂

T₃

Supponiamo ci sia uno sbilanciamento su X (pari a 2) per la differenza tra le altezze di T1 e T3.

h + 2

h + 3

h

h + 1 h

X Y

T₁

T₂ T₃

h + 1 h + 2

h h + 1

h

beta = 2 beta = 0

Rotazione a DX

L’altezza del sottoalbero precedentemente radicato in X decresce di uno

(8)

ALBERI AVL

RIBILANCIAMENTO - CASO SD

Supponiamo ci sia uno sbilanciamento su X (pari a 2).

Rotazione a SX su Z

La prima rotazione non risolve lo sbilanciamento

Z X Y

T₃ T₀

T₁ T₂

h + 3 h + 2

h

h; h − 1

h + 1 h

h; h − 1

beta = 2

Z

X

Y

T₃

T₀ T₁

T₂

h + 3

h + 2

h

h + 1

beta = 2

h

Solo uno tra T1 e T2 ha altezza h

h; h − 1

(9)

ALBERI AVL

RIBILANCIAMENTO - CASO SD

h

Rotazione a DX

L’altezza del sottoalbero precedentemente radicato in X decresce di uno

Z

Y X

T₃ T₀ T₁ T₂

h + 2

h h; h − 1 h + 1

h; h − 1

h + 1 Z

X

Y

T₃

T₀ T₁

T₂

h + 2

h + 1

beta = 2

h

h; h − 1

h + 3 ^{beta = 0}

(10)

ALBERI AVL

INSERIMENTO

Inseriamo il nodo “19”

15

7

4 11

23

0 0 32 0

0 1

0

19

(11)

ALBERI AVL

INSERIMENTO

15

7

4 11

23

0 0 32 0

0 1

0

19

Stack dei nodi visitati

15

(12)

ALBERI AVL

INSERIMENTO

15

7

4 11

23

0 0 32 0

0 1

0

19

15 23

(13)

ALBERI AVL

INSERIMENTO

15

7

4 11

23

0 0 32 0

0 1

0

19

15 23

0

Abbiamo inserito il nodo, ora svuotiamo lo stack e aggiorniamo il bilanciamento

(14)

ALBERI AVL

INSERIMENTO

15

7

4 11

23

0 0 32 0

0 0

0

19

15

23

0

(15)

ALBERI AVL

INSERIMENTO

15

7

4 11

23

0 0 32 0

0 0

0

19

15

0

(16)

ALBERI AVL

INSERIMENTO

(17)

ALBERI AVL

INSERIMENTO

▸ Il caso migliore è quello in cui non otteniamo nessun

valore

+2 −2

o e aggiorniamo solamente il bilanciamento

(18)

ALBERI AVL

INSERIMENTO

valore

+2 −2

▸ Notate come se c’è uno sbilanciamento, esso deve essere con un valore , dato che l’aggiunta di un nodo modifica l’altezza di al più .

±2 1

(19)

ALBERI AVL

INSERIMENTO

valore

+2 −2

▸ Notate come se c’è uno sbilanciamento, esso deve essere con un valore , dato che l’aggiunta di un nodo modifica l’altezza di al più .

±2 1

▸ Nel caso vi sia sbilanciamento cerchiamo il primo nodo — risalendo dal nodo appena inserito — che è sbilanciato - e applichiamo uno degli schemi di rotazione visti prima.

(20)

ALBERI AVL

INSERIMENTO

(21)

ALBERI AVL

INSERIMENTO

▸ Ma come facciamo a provare che queste operazioni rendono un albero bilanciato?

(22)

ALBERI AVL

INSERIMENTO

▸ Non è direttamente intuitivo, lo proviamo per un caso (sinistra-sinistra), per gli altri casi è equivalente

(23)

ALBERI AVL

INSERIMENTO

▸ Non è direttamente intuitivo, lo proviamo per un caso (sinistra-sinistra), per gli altri casi è equivalente

▸ Associamo ad ogni nodo la sua altezza e vediamo come questa viene modificata dalle operazioni di rotazione

(24)

ALBERI AVL

INSERIMENTO

Se effettuiamo la rotazione notiamo come la proprietà degli alberi AVL venga ripristinata

X

Y

T₁ T₂

T₃

h + 2

h + 3

h

h h; h − 1

X Y

T₁

T₂ T₃

h + 1 h + 2

h

beta = 2 beta = 0

Rotazione a DX

h

Qui vediamo che lo sbilanciamento è causato dal fatto che inserire il nodo nuovo

fa crescere l’altezza di T1, di Y e di X. In particolare l’altezza di X prima dell’inserimento è h+2, e l’altezza del nodo Y, che sostituisce X, dopo la rotazione è di nuovo h+2.

Non solo l’albero si ribilancia, ma anche ogni antenato di X torna ad essere bilanciato.

h; h − 1

(25)

ALBERI AVL

INSERIMENTO

(26)

ALBERI AVL

INSERIMENTO

▸ Abbiamo visto che per un caso le rotazioni ribilanciano il sottoalbero.

(27)

ALBERI AVL

INSERIMENTO

▸ Queste rotazioni possono creare problemi più in altro nell’albero?

(28)

ALBERI AVL

INSERIMENTO

▸ No, perché l’albero ottenuto dopo le rotazioni ha esattamente la stessa altezza dell’albero prima dell’inserimento

(29)

ALBERI AVL

INSERIMENTO

▸ No, perché l’albero ottenuto dopo le rotazioni ha esattamente la stessa altezza dell’albero prima dell’inserimento

▸ Quindi se i nodi antenati erano bilanciati prima dell’inserimento lo rimangono anche dopo

(30)

ALBERI AVL

INSERIMENTO

15

7

4

23

0 32

0 -1 1

0

25

(31)

ALBERI AVL

INSERIMENTO

15

7

4

23

0 32

0 -1 1

0

25

15

(32)

ALBERI AVL

INSERIMENTO

15

7

4

23

0 32

0 -1 1

0

25

15 23

(33)

ALBERI AVL

INSERIMENTO

15

7

4

23

0 32

0 -1 1

0

25

15 23

32

(34)

ALBERI AVL

INSERIMENTO

15

7

4

23

0 32

0 -1 1

0

25

15 23

32

0 Inseriamo il nodo ed iniziamo ad aggiornare lo sbilanciamento

(35)

ALBERI AVL

INSERIMENTO

15

7

4

23

0 32

-1 -1 1

0

25

15 23

32

0

(36)

ALBERI AVL

INSERIMENTO

15

7

4

23

0 32

-1 -1 2

0

25

15

23

0

Abbiamo trovato il primo nodo sbilanciato: caso destra-sinistra

(37)

ALBERI AVL

INSERIMENTO

15

7

4

25

0 32 0

-1 0

0

23

15

0

Abbiamo ribilanciato l’albero

(38)

ALBERI AVL

CANCELLAZIONE

(39)

ALBERI AVL

CANCELLAZIONE

▸ La cancellazione avviene come per un Albero Binario di Ricerca, ma rimuovendo un nodo si può creare uno sbilanciamento.

(40)

ALBERI AVL

CANCELLAZIONE

▸ Utilizzando gli schemi di rotazioni visti prima possiamo ribilanciare.

(41)

ALBERI AVL

CANCELLAZIONE

▸ In questo caso però, l’altezza dopo il ribilanciamento descresce di una unità rispetto a prima della cancellazione.

(42)

ALBERI AVL

CANCELLAZIONE

▸ In questo caso però, l’altezza dopo il ribilanciamento descresce di una unità rispetto a prima della cancellazione.

▸ Quindi potremmo dover ribilanciare anche in tutti i nodi antenati. Quindi la cancellazione costa O(h) passi.

(43)

ALBERI AVL

CANCELLAZIONE

Se effettuiamo la rotazione notiamo come la proprietà degli alberi AVL venga ripristinata

X

Y

T₁ T₂

T₃

h + 2

h + 3

h

h + 1 h

X Y

T₁

T₂ T₃

h + 1 h + 2

h

beta = 2 beta = 0

Rotazione a DX

h + 1

Vediamo che l’albero torna ad essere bilanciato ma l’altezza decresce di uno.

h

(44)

ALBERI AVL

ALBERI AVL

(45)

ALBERI AVL

ALBERI AVL

▸ Gli alberi AVL sono alberi con profondità

O(log n)

(46)

ALBERI AVL

ALBERI AVL

O(log n)

▸ Le operazioni di ricerca non cambiano rispetto agli alberi binari di ricerca normali

(47)

ALBERI AVL

ALBERI AVL

O(log n)

▸ Le operazioni di inserimento e rimozione rimangono , con l’altezza dell’albero, quindi

h O(log n) O(h)

(48)

ALBERI AVL

ALBERI AVL

O(log n)

▸ Le operazioni di inserimento e rimozione rimangono , con l’altezza dell’albero, quindi

h O(log n) O(h)

▸ Richiedono però informazione aggiuntiva salvata nei nodi (come minimo bit/nodo)