Alberi di Ricerca Binari

Consideriamo l’algebra “parti di A ordinato” (PAO) così costituita:
PAO = A, Subset(A), Bool, Membro, Inserisci, Elimina, Minimo, \emptyset , a_1, a_2, \dots , a_n

Dove:

  • A è un insieme totalmente ordinato di elementi (A = \{ a_1, a_2, \dots , a_n \} , \le )
  • Subset(A) è una famiglia di sottoinsiemi di A
  • \emptyset è l’insieme vuoto
  • Bool è l’insieme composto dagli elementi “vero e falso” (Bool = \{ vero, falso \} )

Le operazioni eseguibili sono riprese dall’algebra precedente, fatta eccezione per la funzione minimo che viene così definita:

  • Minimo(Y) = min \{x \mid x \in Y \}

Gli Alberi di Ricerca Binari (ARB) sono particolari strutture dati utilizzate per mantenere in memoria dati aventi particolari relazioni. All’interno di un ARB i figli di un dato nodo sono suddivisi in nodi di sinistra e nodi di destra in modo tale che i figli posizionati a sinistra abbiano sempre valore inferiore a quello del nodo padre e che i figli posizionati a destra abbiano sempre valore superiore. Abbiamo trattato gli alberi binari nel capitolo Strutture dati e Applicazioni in C.

Consideriamo un sottoinsieme S di A ( S \subseteq A ), un albero di ricerca binaria per S è un albero binario T , in cui i vertici sono etichettati da elementi di s appartenenti a S ( s \in S ).

Ogni vertice v presenta un etichetta E[v] tale che:

  1. Per ogni elemento s \in S , esiste uno e un solo vertice v in T , tale che E(v) = s ;
  2. Per ogni vertice v , se u è un vertice del sotto-albero sinistro di v , allora E(u) < E(v) ;
  3. Per ogni vertice v , se u è un vertice del sotto-albero destro di v , allora E(u) > E(v) .

Consideriamo ad esempio il vettore S = (animale, è, feroce, la, pecora, un) ottenuto in seguito all’ordinamento lessicografico delle parole sull’insieme S = { a, pecora, è, un, animale, feroce}.

Possiamo esprimere il vettore attraverso il seguente albero di ricerca binaria:
algo_datibis1

Il vettore S definisce quindi l’associazione tra l’indice dell’albero e l’etichetta, mentre l’insieme S definisce l’ordinamento fornendo la radice dell’albero.

Implementazione degli Alberi di Ricerca Binari

Gli alberi di ricerca binaria possono essere implementati mediante tabelle oppure, come già avviene per gli alberi binari, per mezzo di record. È possibile utilizzare un’unica tabella così strutturata:

algo_datibis2

L’analisi dell’array parte dal blocco centrale e prosegue poi con l’analisi dei centri delle rispettive sottosezioni. Indichiamo con ‘/’ l’assenza di una parola. In alternativa è possibile utilizzare quattro tabelle distinte contenenti l’etichetta dei nodi e le informazioni strutturali:

Etichetta
1 animale
2 è
3 feroce
4 pecora
5 un
6 la
Padre
1 4
2 3
3 1
4 0
5 4
6 6
Destra
1 0
2 0
3 0
4 5
5 6
6 0
Sinistra
1 3
2 0
3 2
4 1
5 0
6 0

La soluzione migliore sarebbe comunque l’implementazione per mezzo di record. Le procedure eseguibili su un albero binario sono:

  • Minimo(r) , ricerca il vertice con etichetta minima all’interno del sotto-albero di v ;
  • 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 etichettato come x all’interno del sotto-albero con vertice v . Anche in questi casi è opportuno preservare la struttura dell’albero.

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 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 sin(v) != 0 do
    v := sin(v)
  end while

  return v
end

Procedura Cerca

La procedura verifica la presenza del nodo x all’interno del sotto-albero con vertice v , la procedura viene implementata in modo ricorsivo.

Procedura Cerca(v, x)
begin
  if E(v) = x then
    return vero
  else if E(v) > x then

    if sin(v) != 0 then
      return Cerca(sin(v), x)
    else
      return falso
    end if

  else if E(v) < x then

    if des(v) != 0 then
      return Cerca(des(v), x)
    else
      return falso

  end if

end

È possibile modificare la procedura facendo sì che essa ritorni l’indice dell’elemento trovato. Per fare questo è sufficiente modificare:

return vero

in:

return 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 inserisce un nuovo nodo all’interno del sotto-albero con vertice v . In questi casi è importante preservare la struttura dell’albero.

Procedura Inserisci(v, x)
begin
  if E(v) > x then

    if sin(v) != 0 then
      Inserisci(sin(v), x)
    else
      Crea_nodo_sin(v, x)
    end if

  else if E(v) < x then

    if sin(v) != 0 then
      Inserisci(sin(v), x)
    else
      Crea_nodo_des(v, x)
    end if

  end if
end

Le procedure Crea_nodo_sin e Crea_nodo_des inseriscono nelle tabelle dell’albero di ricerca i dati relativi al nuovo nodo. Di seguito vediamo come esempio la strutture della procedura Crea_nodo_sin. Essa aggiunge un nuovo nodo u , figlio sinistro di v dal valore x .

Procedura Crea_nodo_sin(v, x)
begin
  creo un nuovo nodo u
  etichetta(u) := x

  sin(u) := 0

  des(u) := 0
  sin(v) := u

  padre(u) := v
end

Procedura Elimina

La procedura elimina il nodo x all’interno del sotto-albero con vertice v . Anche in questi casi è opportuno preservare la struttura dell’albero. La procedura Elimina, a differenza delle precedenti, deve fare un largo uso delle tabelle degli alberi al fine di mantenere la struttura dell’albero binario.

I passi che portano all’eliminazione del dell’albero sono:

  1. Identificare il nodo v da eliminare, tale che: E(v) = x ;
  2. Procedere con l’analisi del nodo:
    1. Se v non ha figli, quindi è una foglia dell’albero, si elimina la riga corrispondente all’interno delle tabelle dell’albero;
    2. Se v ha un solo figlio:
      1. Se v è la radice dell’albero e ha un solo figlio u , si elimina v dalle tabelle dell’albero e si inserisci \emptyset nella corrispondente riga di u nella tabella “padre”;
      2. Se v non è radice e ha un solo figlio u , si elimina v dalle tabelle del grafo e si collega direttamente u con padre(v) , agendo nelle tabelle corrette;
    3. Se v ha due figli:
      1. Si determina il vertice v_m , con etichetta massima all’interno del sotto-albero sinistro di v . Si inserisce l’etichetta di v_m al posto di quella di v e si esegue la procedura togli(v_m) relative al punto 2b.

Per sintesi chiamiamo togli(v) la procedura che esegue i passaggi del punto 2a e 2b.

Procedura Togli(v)
begin
  if (sin(v) = 0 ʌ des(v) = 0) then
    rimuovo 'v' dalle tabelle dell'albero
  else if (padre(v) = 0 ʌ ((sin(v) = 0 ʌ des(v) != 0) v (sin(v) ʌ des(v) = 0)) then
    rimuovo 'v' dalle tabelle dell'albero e impongo padre(u) := 0
  else if (padre(v) != 0 ʌ ((sin(v) = 0 ʌ des(v) != 0) v (sin(v) ʌ des(v) = 0)) then
    rimuovo 'v' dalle tabelle dell'albero e impongo sin(padre(v)) := u oppure des(padre(v)) := u
end

Il passo 2c richiede una particolare procedura in grado di eseguire il calcolo del vertice massimo nel sotto-albero sinistro di v , denotiamo questa procedura con il nome Massimo.

Procedura Massimo(r)
begin
  v := r
  while des(v) != 0 do
    v := des(v)
  end while

  return v
end

Andiamo ora a scrivere il codice della procedura Elimina. La procedura elimina il nodo etichettato come x dal sotto-albero v .

Procedura Elimina(v, x)
begin
  if E(v) < x ʌ sin(v) != 0 then
    Elimina(sin(v), x)
  else if E(v) < x ʌ des(v) != 0 then
    Elimina(des(v), x)
  else if E(v) = x then
    if (v ha al più un figlio) then
      Togli(v)
    else
      vm := Massimo(sin(v))
      E(v) := E(vm)
      Togli(vm)
end

Complessità degli Alberi di Ricerca Binaria

L’algoritmo di ricerca binaria, o dicotomica, esegue nel caso medio un numero di confronti inferiori rispetto al caso medio della ricerca sequenziale ed è per questo da preferirsi. Le procedure descritte richiedono, se applicate ad un albero binario di altezza h , un tempo di calcolo O(h) . Ricordiamo che l’altezza di un albero binario di n nodi è uguale a:
log_{2}n \le h \le n-1

L’esecuzione di n operazioni (MEMBER, INSERT e MIN) richiedono quindi, nel caso peggiore, l’esecuzione in tempo \Theta(n^2) . Le stesse operazioni richiedono invece, nel caso medio, un tempo d’esecuzione uguale a O(n \cdot log_{2}n) .

La sola ricerca binaria opera in un tempo medio uguale a O(log_{2}n) , inferiore al tempo O(\frac{n}{2}) richiesto dalla ricerca sequenziale.

Su un albero di 10 elementi, questo comporta:

  • Ricerca sequenziale, 5 accessi;
  • Ricerca binaria, 3.3 accessi.

Su un albero di 100 elementi, questo comporta:

  • Ricerca sequenziale, 50 accessi;
  • Ricerca binaria, 6.6 accessi.

e così via…