Summaries

template <class T>
class AlberoB {
    protected:
        SNodo* pradice;
    public:
        AlberoB():
        AlberoB(const T& value);
        bool nullo() // => radice == null
        bool figlio() // => se entrambi i figli sono nulli
        AlberoB figlio (Direzione d) const
        // ...
}

Metodi utili implementati da noi

• Ci fornisce la profondità di un albero.

  int profondo(Albero<T> A) {
  if(A.nullo()) return 0;
  
  int p1 = profondo(A.figlio(DES));
  int p2 = profondo(A.figlio(SIN));
  
  return 1 + max(p1, p2);
  }

  Questo tipo di risoluzione è del tipo BOTTOM UP, cioè si risolve prima ciò che sta in basso (NODO FOGLIA) e poi ricostruisci.

• Fornisce se l'albero è bilanciato.

  bool bilanciato(Albero<T> A) {
  if(A.nullo()) return true;
  
  int p1 = profondo(A.figlio(DES));
  int p2 = profondo(A.figlio(SIN));
  
  return(abs(p1-p2) <= 1) && bilanciato(A.figlio(DES)) && bilanciato(A.figlio(SIN));
  }

  Poco efficiente, vado a ricontrollare nodi che ho già visto visitato (circa O(esponenziale)). Sviluppiamola in maniera differente.

  bool bilanciato(Albero<T> A, int& prof) {
  if(A.nullo()) {
      prof = 0;
      return true;
  }
  
  int profD, profS;
  int s1 = bilanciato(A.figlio(DES), profD);
  int s2 = bilanciato(A.figlio(SIN), profS);
  
  return s1 && s2 && abs(profD+profS) <= 1;
  // complessita' O(n)
  }

Visita di alberi binari

Possiamo individuare quattro tipi di algoritmi di visita:

1. visita in preordine, valuto il contenuto della radice e poi visito tutto il sotto-albero sinistro e poi il destro → A L E R B O
2. visita simmetrica, visito tutto l'albero sinistro, valuto la radice e poi tutto il sotto-albero destro → E L R A B O
3. visita in postordine, visito tutto sinistra poi tutta a destra e poi stampo → E R L O B A
4. visita per livelli, visita tutti i nodi livello per livello → A L B E R O

I tre tipi di algoritmo si chiamano deep first search (DFS) che visitano in profondità mentre l'ultimo algoritmo si chiama breadth first search (BFS) che visitano in ampiezza.

Vediamo la codifica di un algoritmo deep first search (DFS):

void visitaDFS(AlberoB A) {
    if(A.nullo()) return;

    A.radice(); // la pos. di questa istruzione determina il tipo di DFS
    visitaDFS(A.figlio(SIN));
    visitaDFS(A.figlio(DES));
}

Attraverso le viste possiamo risolvere la maggior parte dei problemi degli alberi.

Albero binario di ricerca

Non sono altro che alberi in cui vige una regola di ripartizione degli elementi. In particolare è detto albero binario se per ogni nodo v di esso, tutti i nodi nel sotto-albero sinistro di v precedono v e tutti i nodi del sotto-albero destro non precedono v.

Le operazioni fondamentali sono cercare/inserire/cancellare un oggetto. La ricerca in un albero binario, nel caso essa sia pure bilanciato, ha complessità pari a O(log₂ n).

I vantaggi di usare un albero rispetto ad altre strutture dati sono:

• struttura dinamica → niente spreco di spazi
• velocità d'inserimento → O(log₂ n)

Stampa ordinata dei valori contenuti in un albero binario di ricerca avviene tramite vista simmetrica.

È utile avere metodi di manutenzione dell'albero, ad esempio l'auto-bilanciamento. Questo può avvenire creando un vettore temporaneo ordinato e poi andando a dividere gli elementi, inserendo l'elemento centrale all'interno dell'albero.