Alberi 2-3

Gli Alberi 2-3 sono una particolare implementazione degli Alberi B (che vedremo in seguito), che permettono di eseguire le n operazioni viste in precedenza in un tempo di calcolo O(n \cdot log_{2}n) , anche all’interno del caso peggiore. Prima di procedere ricordiamo che ogni albero con n nodi, in cui ogni vertice possiede al più k figli ha altezza maggiore o uguale a log_{k}n . Per eseguire in maniera più efficiente le operazioni viste in precedenza è però necessario che l’albero in questione abbia altezza uguale o prossima a log_{k}n . Per questo motivo chiamiamo Alberi Bilanciati gli alberi con altezza O(log_{2}n) , in cui n è il numero di nodi.

Gli alberi 2-3 sono degli alberi ordinati e bilanciati, in cui ogni nodo che non sia foglia possiede 2 o 3 figli e in cui tutte le foglie hanno la stessa profondità. In un albero 2-3 con n nodi e altezza h ,vale la seguente relazione:

\sum_{k=0}^{h} 2^k \le n \le \sum_{k=0}^{h} 3^k

Calcolando i valori delle somme otteniamo:

2^{k+1}-1 \le n \le \frac{3^{h+1}-1}{2}

Questo implica:

(parte inferiore) log_{3}n \le h \le log_{2}n (parte superiore)

Questa relazione rappresenta una condizione di esistenza per gli alberi bilanciati.

L’insieme di parole S={la, pecora, è, un, animale, molto, feroce} può ad esempio essere rappresentato in questo modo:
algo_datibis3

Implementazione degli Alberi 2-3

Gli alberi 2-3 possono essere rappresentati mediante tre tabelle, in cui rappresentiamo con f_1(v), f_2(v), f_3(v) il primo, il secondo e l’eventuale terzo figlio di v . Rappresentiamo inoltre con L(v) e con M(v) rispettivamente la massima foglia del sotto-albero di radice f_1(v) e la massima foglia del sotto-albero di radice f_2(v) .

f1
1 2
2 animale
3 feroce
4 molto
f2
1 3
2 è
3 la
4 pecora
f3
1 4
2 0
3 0
4 un
L
1 è
2 animale
3 feroce
4 molto
M
1 la
2 è
3 la
4 pecora

Le procedure eseguibili su un albero binario sono:

  • Minimo(r) , calcola il vertice con etichetta minima a partire dalla radice;
  • Cerca(v, x) , verifica la presenza del nodo x all’interno del sotto-albero con vertice v ;
  • Inserisci(v, x) , inserisce un nuovo nodo all’interno del sotto-albero con vertice v . In questi casi è importante preservare la struttura dell’albero;
  • Elimina(v, x) , elimina il nodo x all’interno del sotto-albero con vertice v . Anche in questi casi è opportuno preservare la struttura dell’albero.

Le procedure Inserisci ed Elimina necessitano di due nuove procedure: Riduci e Espandi; le quali saranno incaricate di modificare l’albero ottenuto in seguito all’applicazione delle procedure precedenti, al fine di riottenere un albero 2-3.

Di seguito vediamo l’implementazione di queste procedure in pseudo-codice.

Procedura minimo

La procedura ricerca il vertice con etichetta minima all’interno del sotto-albero 2-3 di v , per trovare questo elemento la procedura accede sempre al nodo figlio di sinistra, fino a che non ne trova più uno.

Procedura Minimo(r)
begin
  v := r               // inizializzazione
  while f1(v) != 0 do
    v := f1(v)
  end while
  return v
end

Procedura Cerca

La procedura verifica la presenza del nodo a all’interno del sotto-albero con vertice v ;

Procedura Cerca(v, a)
begin
  if f1(v) è una foglia then  // il figlio sinistro di 'v' è una foglia? ovvero: 'v' è un "nodo finale"?
    return v
  else if L(v) >= a then      // il valore del figlio massimo del sotto-albero f1 è maggiore del valore 'a'? se si, esamino il sotto-albero
    return Cerca(f1(v), a)
  else if M(v) >= a ∨ f3(v) = 0 then  // il valore del figlio massimo del sotto-albero f2 è maggiore del valore 'a'? oppure, il figlio 3 esiste?
    return Cerca(f2(v), a)
  else                        // altrimenti esamino il sotto-albero del terzo figlio
    return Cerca(f3(v), a)
end

La procedura è così sviluppata, sia \{ a_1, a_2, \dots , a_n \} l’insieme rappresentato dall’albero, con a_1 < a_2 < \dots < a_n . Per ogni valore a \in A e ogni nodo interno v , la procedura Cerca(v, a) restituisce un nodo intero p , appartenente al sotto-albero di v , i cui figli sono foglie e al verificarsi della seguente proprietà: se a_i è l’eventuale elemento di A che precede il più piccolo figlio di p , e se a_j è l’eventuale elemento di A che segue il più grande figlio di p , allora si verifica che: a_i < a < a_j .

algo_datibis4

Consideriamo ad esempio l’insieme A = {la, pecora, è, un, animale, molto, feroce} e ricerchiamo all’interno dell’albero ottenuto da A il valore a = “la”.

algo_datibis5

La procedura Cerca(1, ``la'') restituisce il nodo “3”.
Ecco il perché della riga 3 dell’algoritmo:

if f1(v) è una foglia then

Non mi interessa sapere esattamente in quale figlio di v si trova l’elemento a , mi basta sapere che l’elemento a si trova in un figlio di v . La procedura Membro, che verifica se un elemento appartiene o no alla struttura dati, può essere implementata eseguendo la procedura Cerca sulla radice dell’albero.

Procedura Inserisci

La procedura Inserisci, così come la successiva procedura Elimina, richiede la preventiva scrittura della funzione Cerca, al fine di inserire o cancellare il nodo a ai/dai figli di p .Queste procedure tuttavia, possono generare dei problemi nelle situazioni in cui l’inserimento o l’eliminazione di un nodo fa venir meno le condizioni di esistenza di un albero 2-3.

Non è ad esempio possibile inserire un nodo ad un nodo che ha già 3 figli. Per risolvere questi problemi vengono implementate le procedure Riduci ed Espandi, da richiamare al termine del processo di inserimento/eliminazione.

La procedura Riduci si occupa ad esempio della modifica degli eventuali sottoalberi composti da 4 nodi che si possono creare in seguito alle operazioni di inserimento.

Procedura Riduci(v)
begin
  if v ha 4 figli
    creo un nuovo nodo 'u'
    assegno ad 'u' i primi due figli di 'v'
    aggiorno i valori f1, f2, f3 di 'v' e di 'u', e in seguito, i valori di "padre" dei vari nodi

    if padre(v) = 0 then   // v è radice
      creo una nuova radice 'r'
      f1(r) := u
      padre(u) := r
      f2(r) := v
      padre(v) := r
    else
      w := padre(v)   // w è il padre di v
      impongo 'u' figlio di 'w' precedente a 'v'
      Riduci(w)
    end if
  end if
end

Passiamo ora alla scrittura della procedura Inserisci.

Procedura Inserisci(r, a)
begin
  p := Cerca(r, a)
  if f1(p) != a ⋀ f2(p) != a ⋀ f3(p) != a then  // se 'a' non è già figlio di 'p'
    aggiungo 'a' ai figli di 'p'
    Riduci(p)
end

In modo analogo si può procedere con l’implementazione della procedura Elimina e della relativa procedura Espandi.

Esempio d’inserimento

Vediamo, ad esempio, come si comporta la procedura di inserimento quando agisce sul seguente albero 2-3, rappresentante l’insieme delle lettere {a, c, e, f, g, h, i}.

algo_datibis6

Per inserire la lettera d eseguiamo la procedura Inserisci(r, d) , al fine di ottenere il seguente albero 2-3:

algo_datibis7

In sintesi:

  1. La procedura Inserisci(r, d) richiama Cerca(r, d) che restituisce il nodo “e-f”;
  2. Aggiungendo ‘d’ al nodo “e-f” (ora nodo “d-f”) si fa venir meno la condizione di esistenza degli alberi 2-3, per questo motivo viene richiamata la procedura Riduci(d-f) ;
  3. La procedura Riduci(d-f) inserisce due nuovi figli nella radice “c-g”, e poi richiama se stessa su quest’ultima;
  4. L’esecuzione di due procedure Riduci() sulla radice porta al risultato sopra rappresentato.

Complessità degli Alberi 2-3

Ogni procedura di modifica dell’albero binario deve necessariamente includere i passaggi utili a modificare i valori presenti nelle tabelle L e M di tutti i nodi presenti lungo il cammino del generico nodo p modificato. Per questo motivo, il processo di aggiornamento delle tabelle può spesso procedere fino alla radice, anche il processo di aggiornamento dei nodi si è arrestato in precedenza.

Ricordando la definizione iniziale:

(parte inferiore) log_{3}n \le h \le log_{2}n (parte superiore)

Da qui otteniamo il tempo peggiore richiesto per l’esecuzione delle operazioni sopra descritte, nell’ordine di O(log_{2}n) . Il costo di esecuzione è ancora una volta totalmente dipendente dall’altezza dell’albero e quindi dal tempo necessario a percorrere la distanza radice → nodo.