Albero binario: differenze tra le versioni

Versione delle 01:38, 12 nov 2023

Versione attuale delle 08:07, 23 mag 2025

(2 versioni intermedie di 2 utenti non mostrate)

Riga 1:

{{F|informatica|ottobre 2015|}}

{{Organizzare|La voce sarebbe da riscrivere in un tono meno colloquiale (ad es. "In questa sezione trattiamo..."). La sezione "Implementare gli alberi di ricerca binari su array" sarebbe forse da spostare nella pagina "Albero binario di ricerca". Inoltre la sezione "Algoritmi elementari su alberi binari" sarebbe da sistemare secondo il manuale. Per riorganizzare la pagina si potrebbe prendere spunto da quella su en.wiki|informatica|gennaio 2024}}

[[File:Binary tree.svg|miniatura|Un albero binario]]

In [[informatica]] un '''albero binario''' è ununa [[struttura dati]] ad [[albero (grafo)|albero]] i cui [[Nodo (grafi)|nodi]] hanno [[Glossario di teoria dei grafi#Grado di un vertice|grado]] compreso tra 0 e 2. Per ''albero'' si intende un [[grafo]] non diretto, connesso e aciclico mentre per ''grado'' di un nodo si intende il numero di sotto alberi del nodo, che è uguale al numero di figli del nodo.

Anche l'albero costituito da un solo nodo e nessun [[arco (teoria dei grafi)|arco]] si considera un albero binario valido, sebbene il grado del nodo in questo caso sia nullo.

Riga 33 ⟶ 34:

'''Profondità di un albero''': La radice r ha profondità 0, i suoi figli sinistro e destro, hanno profondità 1, i nipoti profondità 2 e così via. Quindi se la profondità di un nodo è p i suoi figli non vuoti hanno profondità p+1

Per quanto riguarda l{{'}}'''altezza''' h di un albero binario è data dalla massima profondità raggiunta dalle sue foglie. Quindi, l'altezza misura la massima distanza di una foglia dalla radice dell'albero, in termini di numero di archi attraversati.

Poiché la definizione di alberi si applica anche ai sotto alberi, è più efficiente e semplice trovare l'altezza di un albero binario osservando che l'albero composto da un solo nodo ha altezza pari a 0, mentre un albero con almeno due nodi ha altezza pari all'altezza del suo sottoalbero più alto, incrementata di uno in quanto la radice introduce un ulteriore livello

<div style="text-align:center;">'''''h=profondità del più lungo cammino'''''</div>