Albero binario di ricerca

Un albero binario di ricerca (da qui in avanti indicato anche come 'ABR'), in contesto informatico, è un Albero binario in cui i valori dei figli di un nodo sono ordinati, usualmente avendo valori minori di quelli del nodo di partenza nei figli a sinistra e valori più grandi nei figli a destra.

L'origine è da attribuirsi a più persone intorno alla fine degli anni '50.

Definizione formale

La definizione formale di un ABR è quella di un Albero binario $T$ avente le seguenti tre proprietà, in cui indicheremo come $val(x)$ il valore di un nodo $x\in T$ :

$\forall \;x\in T,val(x)\in C$ dove $C$ è un insieme parzialmente ordinato
$\forall \;x\in T,y\in T:y\in sinistra(x)\to val(y)\leq val(x)$ dove $sinistra(x)$ rappresenta il sottoalbero sinistro di un nodo $x\in T$
$\forall \;x\in T,y\in T:y\in destra(x)\to val(y)\geq val(x)$ dove $destra(x)$ rappresenta il sottoalbero destro di un nodo $x\in T$

Implementazione

In generale, l'implementazione dell'ABR è uguale a quella di un Albero binario, in quanto sono le operazioni poi a imporre le proprietà all'albero.

Ad esempio, in linguaggio Pascal l'implementazione di un ABR contenente dei semplici interi è uguale a quella di un albero binario contenente semplici interi:

type 
   ABR = ^nodo;
   nodo = record 
             valore:integer;
             sinistra:ABR;
             destra:ABR;
          end;

Operazioni

Per le operazioni più comuni su un ABR contenente $n$ elementi, sfruttando anche le sue proprietà, sono stati trovati algoritmi con complessità nell'ordine di $O(h)$ con $h$ pari alla profondità dell'ABR stesso, tranne che per la visita di tutti i nodi (svolta in complessità $O(n)$ ).

Essendo l'ABR un Albero binario, nel caso migliore si ha quindi $h=\log _{2}n$ dove $n$ è il numero di nodi dell'albero.

Visita ordinata

Una prima operazione è la visita di tutti i suoi elementi in maniera ordinata, ovvero dall'elemento più piccolo all'elemento più grande.

Algoritmo

La visita è effettuata con un algoritmo ricorsivo che sfrutta le proprietà dell'ABR, visitando prima in maniera ordinata il sottoalbero sinistro, poi visitando il nodo radice e infine visitando in maniera ordinata il sottoalbero destro.

Poiché vengono visitati tutti i nodi una sola volta, la complessità algoritmica è pari a $O(n)$ .

Implementazioni

Una implementazione d'esempio in linguaggio Pascal è la seguente:

Procedure VisitaOrdinata(T:ABR)
begin
  if (T<>nil) then
  begin
    VisitaOrdinata(^T.sinistra);
    Visita(^T.valore);
    Visita(^T.destra);
  end;
end;

Ricerca di un elemento

La ricerca del nodo contenente un certo valore è una delle operazioni più frequenti su un ABR.

Algoritmo

L'algoritmo risolutivo è anche in questo caso ricorsivo, e sfruttante le caratteristiche dell'ABR. La ricerca è svolta confrontando il valore della radice dell'ABR con quello da trovare, e se non si è trovato il valore cercato, svolgendo la ricerca sul sottoalbero sinistro o destro a seconda se la radice dell'ABR ha un valore maggiore o minore di quello cercato.

L'algoritmo a ogni passo ricorsivo scende un livello dell'albero, quindi è evidente che la sua complessità algoritmica è $O(h)$ , dove $h$ è la profondità dell'albero.

Implementazioni

Una implementazione dell'algoritmo in linguaggio Pascal è la seguente:

Function Ricerca(T:ABR, y: integer):ABR
begin
  if (T=nil) or (^T.valore=y) then
     Ricerca:=T;
  else
     if (^T.valore<y) then
        Ricerca:=Ricerca(^T.destra,y);
     else
        Ricerca:=Ricerca(^T.sinistra,y);
end;

Inserimento di un elemento

L'inserimento di un elemento in un ABR deve essere fatta in maniera che l'albero risultante dopo l'inserimento deve rispettare sempre le proprietà degli ABR.

Algoritmo

L'algoritmo è simile a quello della ricerca. In pratica si svolge una ricerca fin quando non si esce dall'albero, e l'ultimo nodo attraversato prima di uscire sarà il padre del nuovo elemento inserito. A questo punto si confronta il valore del padre con quello da inserire e si inserisce adeguatamente a sinistra o destra del padre il nuovo valore.

L'algoritmo ha quindi la stessa complessità algoritmica di quello di ricerca, e quindi $O(h)$ con $h$ la profondità dell'albero.

Implementazioni

Un'implementazione d'esempio in linguaggio Pascal è la seguente:

Procedure Inserisci(var T:ABR, y:integer)
var
  ultimo:ABR;
  attuale:ABR;
  nuovo:ABR;
begin
  ultimo:=nil;
  attuale:=T;
  while (attuale<>nil) do
  begin
    ultimo:=attuale;
    if (^attuale.valore<y) then
       attuale:=^attuale.destra;
    else
       attuale:=^attuale.sinistra;
  end;
  new(nuovo);
  ^nuovo.valore:=y;
  ^nuovo.sinistra:=nil;
  ^nuovo.destra:=nil;
  if ultimo=nil then
     T:=nuovo;
  else
     if ^ultimo.valore<y then
        ^ultimo.destra:=nuovo;
     else
        ^ultimo.sinistra:=nuovo;
end;

Cancellazione di un elemento

La cancellazione di un elemento in un ABR non è un'operazione così semplice. Per mantenere le proprietà dell'ABR anche dopo la cancellazione infatti, bisogna distinguere il caso in cui il nodo da cancellare sia una foglia senza figli, abbia un figlio o abbia due figli.

Algoritmo

L'algoritmo per effettuare la cancellazione quindi innanzitutto distingue i seguenti tre casi:

Se il nodo è una foglia senza figli, basta cancellarlo dall'albero.
Se il nodo invece ha un figlio solo, si elmina sostituendolo nella struttura dell'albero con il suo unico figlio.
Se il nodo invece ha due figli si ricerca il suo successore, e si scambia i valori del nodo da cancellare e del successore trovato, cancellando poi solo quest'ultimo (che ha zero o un figlio solo).

L'algoritmo ha un solo caso in cui fa più di operazioni banali, ed è quando cerca il successore di un nodo.

Quest'ultima operazione è fatta o cercando il minimo del sottoalbero destro del nodo, operazione fatta scendendo i nodi verso sinistra fin quando non si esce dall'albero, e quindi impiegando una complessità massima di $O(h)$ dove $h$ è la profondità dell'albero, visto che a ogni passo ricorsivo si scende di un livello l'albero; o nel caso il sottoalbero destro del nodo non esistesse, salendo l'albero fino a trovare un nodo di cui quello in esame è appartenente al suo sottoalbero sinistro, operazione ricorsiva che anche questa, e che a ogni passo risale un livello dell'albero, impiegando quindi una complessità algoritmica pari a $O(h)$ anche in questo caso.

L'operazione di cancellazione ha quindi una complessità finale $O(h)$ dove $h$ è la profondità dell'albero.

Implementazioni

Una implementazione dell'algoritmo in linguaggio Pascal è la seguente:

Procedure Cancella(var T:ABR, x:ABR)
var
   da_cancellare:ABR;
   precedente:ABR;
   attuale:ABR;
   figlio:ABR;
begin
   if (^x.sinistra=nil) or (^x.destra=nil) then
      da_cancellare:=x;
   else
      da_cancellare:=successore(T,x);
   attuale:=T;
   precedente:=nil;
   while (attuale<>da_cancellare) do
   begin
      precedente:=attuale;
      if (^attuale.valore<^da_cancellare.valore) then
         attuale:=^attuale.destra;
      else 
         attuale:=^attuale.sinistra;
   end;
   if (^da_cancellare.sinistra=nil) then
      figlio:=^da_cancellare.destra;
   else
      figlio:=^da_cancellare.sinistra;
   if (precedente=nil) then
      T:=figlio;
   else 
      if (^precedente.valore<^da_cancellare.valore) then
         ^precedente.destra:=figlio;
      else
         ^precedente.sinistra:=figlio;
   if (da_cancellare<>x) then
       ^x.valore:=^da_cancellare.valore;
   free(da_cancellare);
end;