Differenza tra albero binario e albero di ricerca binario

Albero binario

In informatica, un albero binario (in inglese a binary tree) è una struttura di dati gerarchica in cui ogni nodo ha al massimo due figli generalmente indicati come figlio sinistro e figlio destro. Ciascun nodo in un albero binario contiene tre nodi che includono puntatore al sottoalbero sinistro , e puntatore al sottoalbero e dati elemento di destra . Il nodo più in alto nell’albero è indicato come radice. Di solito un albero vuoto è rappresentato dal puntatore NULL .

Tipi di alberi binari basati sulla struttura

• Albero binario radicato (ha un nodo radice e ogni nodo non ha più di due figli).
• Albero binario completo (ogni nodo dell’albero non ha nessuno o almeno 2 figli).
• Albero degenerato (ogni nodo padre ha un solo nodo figlio. Si comporta come un elenco collegato).
• Albero binario perfetto (tutti i nodi interni hanno 2 figli e le foglie hanno la stessa profondità o lo stesso livello.
• Albero binario completo (ogni livello ad eccezione dell’ultimo livello è completamente riempito e tutti i nodi si trovano alla periferia sinistra.

Albero di ricerca binario

In informatica, gli alberi binari di ricerca  (in inglese binary search trees) sono una struttura di dati utile per l’aggiunta e la rimozione rapida dei dati. L’albero di ricerca binario è un albero binario organizzato in cui esiste un ordine relativo in cui i nodi dovrebbero essere disposti. È composto da nodi, che memorizza i dati e si collega anche a un massimo di altri due nodi figlio. Affinché un albero binario sia un albero di ricerca binario, i dati di tutti i nodi nel sottoalbero sinistro del nodo radice devono essere inferiori ai dati della radice. I dati di tutti i nodi nel sottoalbero destro del nodo radice dovrebbero essere maggiori di quelli uguali ai dati della radice. A questo proposito, le foglie più a sinistra dell’albero hanno i valori più bassi, mentre le foglie a destra dell’albero hanno i valori più alti.

Tipi di albero di ricerca binario

• T-trees
• AVL trees
• Splay trees
• Tango trees
• Red-black trees

Differenza tra albero binario e albero di ricerca binario

CONFRONTO DI BASE	ALBERO BINARIO	ALBERO DI RICERCA BINARIO
Descrizione	L’albero binario è una struttura di dati gerarchica in cui un bambino può avere zero, uno o massimo due nodi figlio, ogni nodo contiene un puntatore a sinistra, un puntatore a destra e un elemento di dati. Non esiste una struttura organizzativa specifica dei nodi nell’albero.	L’albero di ricerca binario è un albero binario organizzato in cui esiste un ordine relativo in cui i nodi dovrebbero essere disposti.
Tipi	Esistono diversi tipi di alberi binari, i più popolari includono: albero binario completo, albero binario completo, albero binario esteso e albero binario perfetto.	I tipi più popolari di albero di ricerca binario includono: alberi a T, alberi AVL, alberi splay, alberi tango, alberi rosso-neri ecc.
Operazioni comuni	Le operazioni comuni che possono essere eseguite su un albero binario sono la cancellazione, l’inserimento e il trasversale.	Gli alberi di ricerca binaria mantengono ordinate le chiavi, quindi la ricerca di solito implementa la ricerca binaria per le operazioni. Gli alberi binari di ricerca sono alberi binari più ordinati che consentono una rapida ed efficiente ricerca, inserimento e cancellazione di elementi.
Descrizione alternativa	L’albero binario può anche essere descritto come una forma di albero specializzata che rappresenta i dati in una struttura ad albero. In un albero binario, il nodo più in alto rappresenta il puntatore alla radice mentre i puntatori alla radice destro e sinistro rappresentano i dati in una struttura ad albero.	L’albero di ricerca binario può anche essere descritto come un tipo di albero binario in cui tutti i nodi nel sottoalbero di sinistra sono minori o uguali al valore del nodo radice e quelli del sottoalbero di destra sono maggiori o uguali a il valore del nodo radice.