Albero binario di ricerca

Poll without page-refresh

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

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.

Indice

1 Definizione formale
2 Implementazione
3 Operazioni
4 Implementare gli alberi di ricerca binari su array
5 Collegamenti esterni

Definizione formale

La definizione formale di un ABR è quella di un Albero binario $T$ avente le seguenti tre proprietà, in cui indicheremo come $v a l (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) \le val(x)$ dove $s i n i s t r a (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) \ge val(x)$ dove $d e s t r a (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);
    VisitaOrdinata(^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 elimina 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;

Implementare gli alberi di ricerca binari su array

Se non è necessario effettuare frequentemente operazioni di inserimento e cancellazioni o non è affatto necessario effettuarle e non si vuole usare troppa memoria è possibile implementare un albero di ricerca binario su un array ordinato, con la restrizione che il numero degli elementi sia $2 n - 1$ con $n \in \N$ .

L'immagine sopra mostra un albero di ricerca binario implementato su un array ordinato di 15 elementi, si comincia ponendo il centro dell'array come radice dell'albero e come sue foglie rispettivamente il centro della parte destra dell'array e il centro della parte sinistra dell'array, si continua applicando ricorsivamente il procedimento fino a che non sono stati coperti tutti gli elementi. Si ottiene quindi l'equivalente dell'albero

la pseudo-algoritmo per la ricerca di una chiave è

Ricerca di una chiave

   N := numero di elementi dell'albero (2^k-1)
   A := array delle N chiavi ordinate in ordine crescente, A[0], A[1] .. A[N - 1]
   key := chiave da cercare
   jump := (N + 1)/4
   i: = (N - 1)/2
   while p > 0 do
       if key == A[i] then
           ricerca finita
       else if key < A[i] then
           i = i - jump
       else if key > A[i] then
           i = i + jump
       endif
       jump = jump / 2
   done
   nessun risultato

.

Collegamenti esterni

BST Implementazione, in linguaggio C(open source), degli algoritmi per la gestione degli alberi binari di ricerca.

Estratto da "http://it.wikipedia.org/wiki/Albero_binario_di_ricerca"

Categoria: Strutture dati

Categoria nascosta: Voci di qualità su pt.wiki

This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.

Giant Panda

Mercedes Car

This site monitored by SitePinger.net