Nella teoria dei grafi , un albero radicato o arborescenza è un grafo aciclico diretto avente un'unica radice e tale che tutti i nodi tranne la radice hanno un singolo genitore.
In informatica , è anche una struttura dati ricorsiva utilizzata per rappresentare questo tipo di grafico.
In un albero ci sono due categorie di elementi:
La radice dell'albero è l'unico nodo che non ha un genitore. I nodi (padri con i loro figli) sono collegati tra loro da una cresta . A seconda del contesto, un nodo può fare riferimento a un nodo interno o esterno (foglia) dell'albero.
La profondità di un nodo è la distanza, cioè il numero di spigoli, dalla radice al nodo. L' altezza di un albero è la massima profondità di una foglia sull'albero. La dimensione di un albero è il suo numero di nodi (contando o meno le foglie), la lunghezza del percorso è la somma delle profondità di ciascuna delle foglie.
Gli alberi possono essere taggati. In questo caso, ogni nodo ha un'etichetta , che è una sorta di "contenuto" del nodo. L'etichetta può essere molto semplice: un numero intero, per esempio. Può anche essere complesso quanto vuoi: un oggetto, un'istanza di una struttura dati, un puntatore, ecc. È quasi sempre obbligatorio poter confrontare le etichette secondo una relazione di ordine totale , al fine di implementare gli algoritmi sugli alberi.
I file e le cartelle in un file system sono generalmente organizzati in una struttura ad albero. Vedi ad esempio l' FHS .
Gli alberi infatti sono usati raramente come tali, ma esistono molti tipi di alberi con una struttura più restrittiva e sono comunemente usati negli algoritmi , soprattutto per la gestione dei database , o per l'indicizzazione dei file. Consentono quindi ricerche rapide ed efficienti. Qui vi diamo gli esempi principali:
Per costruire un albero da scatole contenenti solo informazioni, puoi fare uno dei seguenti tre modi:
Notiamo che esistono altri tipi di rappresentazione specifici per casi particolari di alberi. Ad esempio, l' heap è rappresentato da un array di etichette.
Le passeggiate sugli alberi sono processi di visite ai vertici di un albero, ad esempio per trovare un valore.
Il percorso della larghezza corrisponde a un percorso per livello di nodi dell'albero. Un livello è un insieme di nodi o foglie interni situati alla stessa profondità - si parla anche di un nodo o di una foglia della stessa altezza nell'albero considerato. L'ordine di esplorazione di un dato livello è solitamente conferito, in modo ricorsivo, dall'ordine di esplorazione dei nodi padre - nodi del livello immediatamente superiore.
Quindi, se viene utilizzato l'albero precedente, il percorso sarà A , B , C , D , E , F e G .
Il percorso in profondità è un percorso ricorsivo su un albero. In generale, sono possibili due ordini:
Per gli alberi binari, possiamo anche fare un percorso infisso , vale a dire trattare il nodo corrente tra i nodi sinistro e destro. Quindi, se viene utilizzato l'albero precedente, il percorso sarà D , B , E , A , F , C e G .