I dati vengono comunemente memorizzati in strutture ad albero binario utilizzando algoritmi specializzati . Molti vantaggi provengono da memorizzare i dati in una struttura ad albero . Ad esempio, la ricerca di un albero binario ordinato è molto più veloce di ordinamento di una struttura dati sequenziale ad esempio una matrice . Una struttura di dati ad albero può assumere molti tipi di modelli durante il corso di accesso dati e modifica . La comprensione di questi modelli può aiutare a progettare algoritmi migliori per ottimizzare un algoritmo di albero . Componenti fondamentali di un albero binario

Un albero binario è costituito da nodi, che memorizza i dati e punti ad altri nodi dell'albero . Il nodo radice è il punto di partenza dell'albero e occupa il livello superiore. Si può avere fino a due nodi figlio . Questi nodi figli possono avere fino a due nodi figlio . Il numero di nodi figlio di un dato nodo è chiamato il grado del nodo . Un nodo senza figli e un grado zero è chiamato una foglia . La lunghezza in nodi dal nodo radice al nodo foglia più lontana è l'altezza dell'albero . La profondità di un nodo è la distanza dal nodo radice di esso . Ogni nodo che ha la stessa profondità è detto di essere sullo stesso livello .
Completa Albero binario

Un albero binario completo è un albero in cui ogni nodo ha esattamente due o nullo bambini. In altre parole , ogni nodo ha uno o due figli è una foglia . Un esempio di un albero binario completo è il Binary Decision Diagram , o BDD .
Perfetto albero binario

Un albero binario ideale ha le stesse proprietà del albero binario pieno , ma tutti i nodi foglia sono sullo stesso piano , il che significa che la profondità di tutte le foglie è la stessa in un albero binario perfetto . Dal momento che è anche un albero binario completo , tutti i nodi tranne i nodi foglia hanno un livello di 2 .
Balanced Albero binario

Un albero binario bilanciato è quello in cui la profondità di ogni nodo foglia è o lo stesso o diverso da un valore di uno . Aggiunta e rimozione di nodi da un albero binario bilanciato può sbilanciare , quindi una serie di aggiustamenti chiamato rotazioni devono avvenire per riequilibrare l'albero. Mantenere un albero bilanciato garantisce che il tempo di ricerca medio di ogni nodo è ottimale . Grande carico di lavoro è tenuto a mantenere l'equilibrio di un albero .
Degenerata Albero binario

Un albero binario degenerato è quella in cui tutti i nodi tranne il nodo foglia ha esattamente un nodo figlio . Ha le stesse caratteristiche prestazionali di una lista concatenata , che aumenta il tempo di ricerca di un qualsiasi nodo di una quantità considerevole . Ad esempio, si consideri il caso in cui il nodo cercato è il nodo foglia . L'intero albero deve essere attraversato per trovare questo nodo . Con un albero binario bilanciato , trovando un nodo foglia richiede solo un numero di attraversamenti di nodo pari alla profondità del nodo foglia. Con alberi di grandi dimensioni , la differenza di prestazioni può essere significativo.