ABR di altezza logaritmica

1

Esistono vari criteri di bilanciamento di alberi binari di ricerca che ne garantiscono l’altezza logaritmica. Chiamiamo bilanciato ogni albero binario di altezza logaritmica nel numero dei nodi.

ABR bilanciati in altezzaUn ABR si dice bilanciato in altezza se per ogni nodo v la differenza in valore assoluto tra l’altezza del sottoalbero sinistro di v e l’ altezza del sottoalbero destro di v è ≤ 1.

2

bilanciato in altezza

N.B. Prendiamo come altezza il massimo numero di archi in un cammino radice-foglia. Quindi l’albero vuoto ha altezza -1.

Gli ABR bilanciati in altezza si chiamano brevemente alberi AVL, acronimo dagli autori Georgy Maximovich Adel’son-Vel’skii e Yevgeniy Mikhailovich Landis che li hanno introdotti nel 1962.

Alberi AVL: esempibilanciamento in altezza: per ogni nodo la differenza in valore assoluto tra l’altezza del sottoalbero sinistro di v e quella del sottoalbero destro di v è ≤ 1

3

44

17

32

78

8850

48 620 0

001

12

3 44

17

32

78

50

48 0

0 1

1 2, ma 1-(-1) = 2!3

NON bilanciato: il nodo 78 ha un sotto albero destro di altezza -1, mentre il sotto albero sinistro ha altezza 1, quindi la differenza è 2.

ABR Rosso Neri• alberi rosso-neri, introdotti nel 1972 da Rudolf Bayer, professore

alla Technische Universität München, con il nome di “B-alberi simmetrici”. Leonidas J. Guibas, Professore alla Stanford University e di Robert Sedgewick, professore alla Princeton University ne provano molte proprietà, chiamandoli alberi rosso-neri, in un successivo articolo, apparso nel 1978.

4

J

A

G F

C

E

B D

nil nil

nil nil nil nil nil nil nil

Ogni nodo in un albero rosso-nero è colorato di rosso o di nero, ma la colorazione deve soddisfare dei vincoli che garantiscono che nessun percorso radice-foglia è lungo più del doppio di ogni altro, così l’albero è abbastanza bilanciato da avere altezza logaritmica nel numero dei nodi.

Relazioni tra classi di alberi

5

Alberi bilanciati in altezza

Alberi completi

Alberi quasi completi

Alberi Rosso-Neri

Le operazioniPerchè le operazioni di ricerca, inserimento e cancellazione in un ABR siano di complessità O(log n), dove n è il numero dei nodi dell’albero bisogna modificarle in modo che le eventuali operazioni di ribilanciamento dell’albero siano di complessità O(log n).

Gli alberi bilanciati in altezza o alberi AVL (Adel’son-Vel’skii, Landis, 1962), sono i primi per i quali si ottiene questo risultato poi ottenuto anche per gli alberi rosso-neri (Bayer,1972) e dagli Splay trees (Sleator,Tarjan 1985), che hanno la proprietà che i nodi ricercati vengono spostati verso la radice quindi saranno ricercati più efficientemente in seguito.

Esistono vari altri alberi di ricerca (anche non binari) con i quali possiamo implementare un dizionario di n elementi con operazioi in tempo O(log n). Alcuni di questi, in particolare 2-3 alberi 2-3-4-alberi B-alberi

6

⎬ si trasformano in alberi rosso-neri

Costruzione AVL

7

44

17

44FB = 0

FB=0

FB = 1

Detto FB il fattore di bilanciamento di un nodo, cioè la differenza tra altezza sotto albero sinistro e quella del destro, vediamo alcuni esempi di AVL, cominciando dai più piccoli in termini di numero dei nodi:

44

17 78FB=0 FB=0

FB=0

44

78FB = 0

FB = -1

50

44

17FB=0

FB=1

FB=2!

L’unico AVL con tre nodi!

Esempi di AVL

8

50

44

1778

50

44

1778

48

50

44

17

78

80

tra quelli di altezza 3 ha il minor numero di nodi

FB=0 FB=0

FB=1

FB=1

FB=0 FB=0

FB=0FB=0

FB=1

FB=0 FB=0

FB=1 FB=-1

FB=0

Massima altezza, minimo nodi

9

Ricordiamo che un albero degenere è il più sbilanciato tra tutti gli alberi binari ed è quello di altezza massima a parità di numero di nodi, o anche è quello che a parità di altezza ha il minimo numero di nodi (un solo nodo su ogni livello).

Massimo nodi, minima altezzaL’albero completo è un AVL di altezza logaritmica, e tutti i suoi nodi interni hanno FB = 0 (le foglie avendo sempre FB =0).

10

50

44

17

78

80

FB=0 FB=0

FB=0

48 70

É l’albero AVL che a parità di altezza ha il massimo numero di nodi o anche quello che a parità di numero di nodi ha altezza minima.

Massima altezza, minimo nodi per AVL

Cerchiamo di determinare gli AVL più sbilanciati che possiamo costruire, cioè cerchiamo gli AVL che a parità di altezza hanno il minimo numero di nodi. Il massimo sbilanciamento si ottiene imponendo a tutti i nodi non foglia di avere un FB diverso da 0. Per semplicità stabiliamo che debba essere 1, se prendessimo sempre -1 si avrebbe un risultato equivalente.

11

Alberi AVL “sbilanciati”

12

FB=0

FB = 1

FB = 1

FB=0

FB = 1 FB = 1

FB = 1

FB = 1

FB=0

FB = 1

FB = 1

FB=0

FB = 1

FB = 0

FB = -1 Una scelta “mista” è solo più difficile da gestire, volendo determinare il rapporto tra altezza e numero dei nodi.

La regola di costruzione è: Base: l’albero vuoto è un AVL più sbilanciato a sinistra di altezza -1, T-1, l’albero con un solo nodo è un AVL più sbilanciato a sinistra di altezza 0, T0, Passo induttivo: dati due AVL più sbilanciato a sinistra Th-1 e Th-2 , un nuovo AVL di altezza h si costruisce prendendo un nuovo nodo come radice e come sotto albero sinistro Th-1, l’AVL più sbilanciato a sinistra di altezza h-1 e come sotto albero destro Th-2, quello di altezza h-2.

13

AVL Th-1

AVL Th-2

FB = 1

Alberi AVL: costruzione dei più sbilanciati

Per costruzione tutti i nodi interni di un AVL più sbilanciato a sinistra hanno FB = 1

Esempio costruzione dei più sbilanciati

14

FB = 1 FB = 1

FB = 1

FB = 1

FB = 1

FB = 1

FB = 1FB = 1

FB = 1

FB = 1FB = 1

FB = 1

FB = 1

ogni nodo interno ha un FB = + 1!

Alberi AVL: altezzaIl più piccolo albero AVL più sbilanciato a sinistra non vuoto è

15

44 FB = 0l’albero T0 con h1 = 0 e n1 = 1

44

17FB=0

FB = 1l’albero T1 con h1 = 0 e n1 = 2

Alberi

16

AVL Th-1

AVL Th-2

Fibonacci Fib1 = 1 Fib2 = 1 Fibh = Fibh-1 + Fibh-2

Numero nodi in un AVL più sbilanciato a sinistra di altezza h: n0 = 1 n1 = 2 nh = nh-1 + nh-2 +1 per h≥2

FB = 1

più sbilanciaticalcolo numero dei nodi

Alberi

17

AVL Th-1

AVL Th-2

Fibonacci Fib1 = 1 Fib2 = 1 Fibh = Fibh-1 + Fibh-2

Numero nodi in un AVL più sbilanciato a sinistra di altezza h: n0 = 1 n1 = 2 nh = nh-1 + nh-2 +1 per h≥2

FB = 1

di Fibonaccicalcolo numero dei nodi

Fib1 = 1 e n1 = 2 Per n ≥ 1, si ha Fibh < nh

Alberi di Fibonacci: conclusioneSappiamo che Fibh > φh/51/2 dove φ = 1,618… è la sezione aurea e

usando la relazione Fibh < nh, per h≥1, otteniamo che

φh/51/2 < Fibh < nh

Se prendiamo un albero AVL qualunque di altezza h e con n nodi allora n > nh e

φh/51/2 < n

quindi applicando il logaritmo

h - logφ 51/2 < logφ n e quindi

h < logφ n + logφ 51/2 = O(lg n)18

Alberi AVL: altezza in O(lgn)

19

1. che la loro altezza è in O(lg n), 2. che gli alberi di Fibonacci che sono una classe di alberi AVL che a parità di altezza hanno il minimo numero di nodi.

Per gli alberi AVL abbiamo dimostrato

Poiché per un qualsiasi albero binario T di altezza h si ha che h = Ω(lg n), concludiamo che se T è un qualsiasi albero AVL di altezza h, vale h = θ(lg n)

Alberi AVL: altezza in O(lgn)

20

Senza ricorrere alla crescita dei numeri di Fibonacci possiamo ottenere il risultato cercato esaminando direttamente la ricorrenza

nh= nh-1 + nh-2 +1 per h>2 con casi base

n1 = 1 e n2 = 2

Poiché nh-1 > nh-2 +1 (n3 = n1 + n2 +1 = 4 e l’albero di altezza 3 è l’ultimo che si può costruire aggiungendo solo un nodo nel sottoalbero sinistro)

nh > 2nh-2 per h>2 quindi

nh > 2nh-2 > 22nh-4 >…> 2inh-2i

Da cui nh > 2h/2 . Come prima osservando che se T è un AVL qualsiasi con n nodi e di altezza h si ha n > nh, passando al logaritmo si conclude che lg (n) > h/2 e quindi che h = O(lg n).

Operazioni di ribilanciamentoLe operazioni di inserimento e cancellazione sono le stesse che negli ABR qualunque, ma modificate in modo da poter eventualmente ribilanciare l’albero. Descriviamo nel seguito le operazioni sugli alberi binari che ci consentiranno di ripristinare il bilanciamento in altezza, eventualmente perso in seguito a cancellazioni o inserimenti.

Si tratta di rotazioni.

21

Rotazioni su ABR

22

• Dopo la rotazione l’albero è ancora un ABR, perchè se, b è un nodo in T2 e c in T3 allora vale • A < B < b < C < c .•Richiede tempo O(1)

Rotazione a destra su C

A

B

T2T1

C

T3A

B

T1

T2

C

T3

La doppia rotazione

23

Rotazione a sinistra su A

A

B

T1 T2 T3T4

C

B

A

T2T1

T4

C

T3

B

A

T1 T2

T3

T4

C

Rotazione a destra su C

Si rientra nel caso precedente eliminando lo spigolo, o cammino zig-zag

Esempio di rotazione a sinistra su 5

24

8

3

5

4 7

6 9

2

1

8

x

y

z

3

5

4

7

6

92

1

88

x

y

z

Esempio di doppia rotazione a sinistra su 5

25

8

3

5

4 7

6 9

2

1

8

A

C

B

A

B

3

5

42

1

7

9

6

88

C

3

5

4

6

9

72

1

88

A

B

C

Operazioni su ABR in O(lg n)In un ABR con n nodi e di altezza h le operazioni di • ricerca • inserimento • cancellazione

hanno una complessità asintotica O(h), con lg n ≤ h < n in un albero bilanciato in altezza dimostreremo che hanno una complessità asintotica O(lg n), perchè l’altezza è O(lg n) e il ribilanciamento dell’albero può essere fatto in O(lg n)

26

Esempio inserimento in AVL

27

3

5

4

7

6

92

1

88

FB = 0

FB = -1

FB = 1

FB = 0

FB = -1

3

5

4

7

6

92

1

88

0

Inserimento di 0

FB = 0

FB = 0

FB = 1

FB = 0

FB = -1

INSERIMENTO: aggiornamento FB

28

INSERIMENTO in T1

A

B

T2T1

h-1 h

FB = -1

C

h +1

Risalendo verso la radice il fattore di bilanciamento passa da -1 a 0 quindi l’inserimento ha aumentato l’altezza del sottoalbero sinistro che però era più basso di 1, quindi complessivamente l’altezza del sottoalbero radicato in B non cambia e si può fermare il processo di aggiornamento dei FB. Il caso simmetrico è analogo.

A

B

T2T1

FB = 0

h h

h +1

C

INSERIMENTO: aggiornamento FB

29

INSERIMENTO in T1

A

B

T2T1

h h

FB = 0

C

h +1

Risalendo verso la radice il fattore di bilanciamento passa da 0 a 1 quindi il sottoalbero sinistro ha aumentato la sua altezza e complessivamente tutto il sottoalbero radicato in B, quindi si deve controllare il padre di B. Per esempio se si inserisce come foglia più a sinistra una chiave in un albero completo si dovrà cambiare i FB di tutti i nodi sul cammino più a sinistra portandoli da 0 a 1. Naturalmente il discorso è analogo se FB passa da 0 a -1.

A

B

T2T1

FB = 1

h h+1

h +2

C

Inserimento: CASO LEFT-LEFT

30

inserimento in T1

A

B

T2T1

T3

C

h h

h FB = 0

FB = 1

A

B

T2T1

T3

C

FB = 1

FB = 2

h +2

L’inserimento nel sottoalbero radicato in A può provocare un aumento di altezza nel sottoalbero sinistro di C, nodo nel quale il fattore di bilanciamento diventa illegale.

h h+1

h

h +3

CASO LEFT-LEFT

31

Rotazione a destra su Ch +3

A

B

T1

T2 T3

C

FB = 0

FB = 0

h +2

h+1 h h Dopo la rotazione l’altezza di B è

quella del nodo C prima dell’inserimento, quindi non è necessario risalire ancora verso la radice per ribilanciare l’albero!

A

B

T2T1

T3

C

FB = 1

FB = 2

h h+1

h

CASO LEFT-RIGHT

32

B

A

T1

T4

C

T2

h

hh h+2

FB = 0

FB = 1

T3

inserimento in T2

FB = -1

FB = 2

L’inserimento nel sottoalbero radicato in B può provocare un aumento di altezza nel sottoalbero sinistro di C, nodo nel quale il fattore di bilanciamento diventa illegale.

h

h

h h+3 B

A

T1

T4

C

T3T2

h+1

h-1

FB = 1

LA PRIMA ROTAZIONE

33

FB = 2

A

B

T1

T4

C

T2

T3

Rotazione a sinistra su A

B

A

T1

T4

C

T2

h

h

h h+3

FB = -1

FB = 2

T3

h-1 h

h

h+1

h+3 h-1

h

La seconda rotazione

34

A

B

T1

T4

C

T2

h

h

h+3

FB = 2

T3

Rotazione a destra su C

A

B

T1T4

C

T2 T3

FB = 2

h-1

FB = -1

FB = 0

FB = 0

Anche in questo caso, dopo la seconda rotazione l’altezza di B è quella del nodo C prima dell’inserimento, quindi non è necessario risalire ancora verso la radice per ribilanciare l’albero!

h

hh

h+2

h-1 h

Esempio inserimento

35

A

C

B

3

5

4 7

6 9

2

1

0

-1 -1

-1

00

0 0

8 0

-1

1

-2caso right-right

Rotazione a sinistra su A

1

-1

0

-1

00

0 0

3

64

7

5 92

1

8 0

Inserimento del nodo 8

Esempio inserimento

36

-2

1

1

1 Rotazione a destra su C

0

caso RIGHT- LEFT

35 0

30

60

50 70

65 75

15

10

5

40 55

0 0

0 0

-1

0 0

0 0 0

A

CB

0

35

30

60

50

70

65 75

15

10

540

550 0

-2

0 01

0

00

-1

-1

AB

C

Inserimento del nodo 35

Prof. E. Fachini - Intr. Alg. 37

Rotazione a sinistra su 30

35

30

60

50

70

65 75

15

10

540

550 0

0

-2

0 01

0

00

-1

-1

35

60

50

70

65 75

40 55

30

15

10

5

AB

Ccaso RIGHT- LEFT

00

0

0

0 0

1 0

0

-1

0

0

Complessità

L’ inserimento da solo prende un tempo O(lg n).

Risalendo verso la radice si aggiornano i fattori di bilanciamento nei nodi e se un fattore diventa illegale (-2 o 2) con al più due rotazioni si ripristina la proprietà del bilanciamento in altezza.

Quindi anche le operazioni di ripristino delle proprietà di bilanciamento hanno un costo O(lg n).

38