Alberi AVL

Introduzione

Gli alberi AVL sono delle speciali tipologie di alberi binari di ricerca. Il nome AVL deriva dalle iniziali dei nomi di chi gli scoprì, Adelson-Velskij e Landis.
La loro caratteristica principale è il fatto che garantiscono un’altezza h = O(log n).
Nota: per la stesura del seguente elaborato abbiamo preso ispirazione dal libro Strutture di dati e algoritmi, poiché il Cormen che utilizziamo sempre non tratta diversi particolari di cui andremo a discutere.

Descrizione

Gli alberi AVL fanno parte dell’insieme degli alberi 1-bilanciati, ciò significa che per ogni nodo u deve essere rispettata la seguente condizione:
|h(u.left) – h(u.right)| ≤ 1
In parole significa che per ogni nodo, l’altezza dei suoi due figli differiscono al più di 1. Ricordiamo che in un albero binario, l’altezza di un nodo è la distanza che c’è tra il nodo stesso e una foglia.

Le due proprietà di cui gli alberi AVL godono, ovvero di essere 1-bilanciati ed avere altezza logaritmica, derivano dagli alberi di Fibonacci, che sono un sottinsieme degli alberi 1-bilanciati che raggiungono altezza h col minor numero di nodi possibile, per questo sono detti minimali.
Se eliminiamo un nodo su questo albero, possono accadere due cose:
– l’altezza diminuisce
– l’albero non è più 1-bilanciato
Nessun albero 1-bilanciato con n nodi e altezza h può avere meno di n_h nodi, ossia n ≥ n_h.

Albero di Fibonacci

Un albero di Fibonacci, che chiameremo Fib_h , è definito ricorsivamente: per h = 0 abbiamo un solo nodo n₀ = 1, per h = 1 abbiamo un albero con n₁ = 2 nodi, poi per h > 1, Fib_h è costruito prendendo un albero Fib_h-1 e un albero Fib_h-2, le cui radici diventano i figli di una nuova radice.
Osservando la figura sottostante possiamo vedere meglio che l’albero di dimensione successiva è costruito a partire dai casi precedenti.
Quindi abbiamo che il numero di nodi nell’albero di Fibonacci equivale a
n_h = n_h-1 + n_h-2 + 1
quindi dove 1 è la radice, Fib_h-1 è il sotto albero destro (o sinistro) e Fib_h-2 è il sotto albero sinistro (o destro).
ll nome “Fibonacci” deriva dalla similarità con la formula ricorsiva della serie di Fibonacci, e che quindi la sua dimensione cresce esponenzialmente in modo simile ai numeri di Fibonacci, che dimostreremo in seguito.
Sotto abbiamo messo una figura che rappresenta la costruzione ricorsiva di un albero di Fibonacci, i nodi colorati in verde sono quelli che vengono aggiunti ad ogni passo.

Dimostrazione per induzione che un AF è minimale

Proviamo adesso a dimostrare formalmente che gli alberi di Fibonacci sono 1-bilanciati minimali, ovvero che contengono il minor numero di nodi possibile. Verifichiamo quindi che se togliamo un nodo perdiamo la proprità di 1-bilanciamento o non manteniamo l’altezza h.
Dimostrazione:
Caso base
In Fib₀ l’altezza vale 0, quindi eliminando un nodo l’altezza passa a -1.
In Fib₁ l’altezza vale 1, quindi eliminando un nodo l’altezza passa a 0.
Ipotesi intuttiva: per ogni altezza i < h, Fib_i è minimale.
Passo induttivo
Supponiamo per assurdo che Fib_h non sia minimale, cioè che togliendo un nodo possiamo mantenere altezza h e mantenere la proprietà di 1-bilanciamento. Osserviamo che il nodo da togliere non può essere la radice, altrimenti non sarebbe più un albero, allora il nodo da togliere dovrà appartenere a Fib_h-1 o a Fib_h-2, (vedi figura precente in Fib_h).
Se togliamo un nodo da Fib_h-1 succede che l’altezza passa da h-1 a h-2.
Se togliamo, invece un nodo da Fib_h-2 si perde la condizione di 1-bilanciamento, perché a sinistra abbiamo altezza Fib_h-1, mentre a destra avremo Fib_h-3, allora la radice rimane sbilanciata di 2.
Con questo abbiamo ottenuto una contraddizione che dimostra che l’albero di Fibonacci è 1-bilanciato minimale.

Facciamo adesso altre due dimostrazioni per verificare che un albero di Fibonacci (AF) ha altezza h e dimensione che cresce esponenzialmente come la serie di Fibonacci.

Dimostrazione altezza logaritmica di un albero di Fibonacci

Come anticipato, gli alberi di Fibonacci si chiamano in questo modo perché la loro dimensione cresce in modo simile ai numeri della serie di Fibonacci. La differenza è che c’è in più un +1, quindi,
n_h = n_h-1 + n_h-2 + 1.
Se controlliamo una serie di valori di n_h noteremo che vale la relazione
n_h = F_h+3 – 1.
Dimostriamo allora per induzione.
Caso base
h = 0 -> n₀ = 1, infatti F₀₊₃ – 1 = 2 – 1 = 1
h = 1 -> n₁ = 2, infatti F₁₊₃ – 1 = 3 – 1 = 2

Prima di passare al passo induttivo facciamo un’osservazione.

Sappiamo che per il calcolo dell’h-esimo numero di Fibonacci esiste una formula chiusa:

dobbiamo allora trovare un modo per calcolare anche n_h.
Se guardiamo la tabulazione sottostante notiamo che n_h vale 4 per h = 2 e F_h vale 5 per h = 5.
Inoltre possiamo notare anche che n_h vale 7 per h = 3 e F_h vale 8 per h = 6 e così via.

Questo significa che n_h corrisponde a tre posizioni h in avanti (F_h+3) e poi da quel valore togliamo 1, fatta questa osservazione possiamo dimostrare per induzione che n_h = F_h+3 – 1 per ogni i < h.
Passo induttivo
Ipotesi intuttiva: per ogni altezza i < h, vale n_i = F_i+3 – 1
Dato che n_h = n_h-1 + n_h-2 + 1, allora vale che
1 + (F_(h-1)+3 – 1) + (F_(h-2)+3 – 1) =
1 + F_h+2 – 1 + F_h+1 – 1 =
F_h+3 – 1

Siccome F_h ≥ c^h con c > 1 e h > 2, possiamo dire che n_h = F_h+3 – 1 ≥ c^h.
Sappiamo che n_h è il numero minimo di nodi per un albero di altezza h (perché AF è minimale) e quindi se prendiamo un albero AVL qualsiasi di n nodi, sicuramente n ≥ n_h ,
di conseguenza n ≥ c^h, quindi trasformando questa disequazione abbiamo che h = O(log n).

Inserimento elemento

L’inserimento di un elemento in un albero AVL richiede delle operazioni aggiuntive che servono per garantire che esso assuma la corretta posizione. Per fare questo dobbiamo utilizzare le rotazioni, che spieghiamo in questo articolo -> link.
Qua sotto lasciamo lo psudocodice, che come possiamo vedere è uguale a quello di un normale albero binario di ricerca, soltanto che vengo effettuate delle operazioni aggiuntive, appunto le rotazioni, che servono per il ribilanciamento.

Insert(u, n) {

  if(u = NULL) 
    return u = NewNode(n) //funzione creazione elemento

  else if(n < u.key) {
    u.left = Insert(u.left, n)

    if( Height(u.left) - Height(u.right) == 2 ) {
      if(n > u.left.key)
        u.left = CounterclockwiseRotation(u.left)
      
      u = ClockwiseRotation(u)
    }

  } else {
    u.right = Insert(u.right, n)

    if( Height(u.right) - Height(u.left) == 2 ) {
      if(n < u.right.key) 
        u.right = CounterclockwiseRotation(u.right)
      
      u = ClockwiseRotation(u)
    }
  }

  u.height = max( Height(u.left), Height(u.right) ) + 1

  return u
}