Differenza tra albero binario e albero di ricerca binaria

Cos'è l'albero binario?

L'albero binario è una struttura gerarchica di dati in cui ogni nodo ha zero, uno o al massimo due bambini. Ogni nodo contiene un puntatore "a sinistra", un puntatore "a destra" e un elemento dati. Il puntatore "root" rappresenta il nodo più in alto nell'albero. Ogni nodo nella struttura dati è direttamente connesso a un numero arbitrario di nodi su entrambi i lati, indicati come figli. Un puntatore nullo rappresenta l'albero binario. Non esiste un ordine particolare su come i nodi devono essere organizzati nell'albero binario. I nodi senza nodi figli sono chiamati nodi foglia o nodi esterni.

In termini semplici, definisce una funzione di etichettatura organizzata sui nodi, che a sua volta assegna un valore casuale a ciascun nodo. Tutto ciò che ha due figli e un nodo genitore è un albero binario. Gli alberi binari vengono utilizzati per memorizzare informazioni che formano una gerarchia come il file system sul tuo personal computer. A differenza degli array, gli alberi non hanno limiti superiori sul numero di nodi perché sono collegati tramite puntatori, come gli elenchi collegati. Le funzioni principali di Albero binario includono la rappresentazione di dati gerarchici, l'ordinamento di elenchi di dati, l'esecuzione di operazioni di inserimento / cancellazione efficienti, ecc. I nodi dell'albero sono rappresentati mediante strutture in C.

Che cos'è l'albero di ricerca binaria?

Un albero di ricerca binario è un tipo di struttura dati ad albero binario in cui i nodi sono disposti in ordine, quindi anche chiamato "albero binario ordinato". Si tratta di una struttura dati basata su nodi che fornisce un modo efficiente e veloce di ordinare, recuperare, cercare dati. Per ogni nodo, gli elementi nel sottoalbero sinistro devono essere minori o uguali alla chiave nel suo nodo genitore (LP). Non ci dovrebbero essere chiavi duplicate. In termini semplici, si tratta di un tipo speciale di struttura dati ad albero binario che archivia e gestisce in modo efficiente gli oggetti in memoria.

Permette un rapido accesso alle informazioni, l'inserimento e la rimozione dei dati, inoltre può essere utilizzato per implementare tabelle di ricerca che consentono di cercare gli oggetti con le loro chiavi univoche, come la ricerca del numero di telefono di una persona per nome. Le chiavi univoche sono ordinate in modo organizzato, in modo che la ricerca e altre operazioni dinamiche possano essere eseguite utilizzando la ricerca binaria. Supporta tre operazioni principali: ricerca di elementi, inserimento di elementi e cancellazione di elementi. L'albero di ricerca binario consente un rapido recupero degli elementi memorizzati nell'albero poiché ogni chiave del nodo viene accuratamente confrontata con il nodo radice, che elimina metà dell'albero.

Differenza tra albero binario e albero di ricerca binaria

1. Definizione dell'albero binario e dell'albero di ricerca binaria - L'albero binario è una struttura gerarchica di dati in cui un bambino può avere zero, uno o massimo due nodi figli; ogni nodo contiene un puntatore sinistro, un puntatore destro e un elemento dati. Non c'è un ordine particolare su come i nodi dovrebbero essere organizzati nell'albero. L'albero di ricerca binario, d'altra parte, è un albero binario ordinato in cui esiste un ordine relativo al modo in cui i nodi dovrebbero essere organizzati.
2. Struttura  di Albero binario e albero di ricerca binaria- Il nodo più in alto nell'albero rappresenta il puntatore di root in un albero binario, mentre i puntatori sinistro e destro rappresentano gli alberi più piccoli su entrambi i lati. È una forma specializzata di albero che rappresenta i dati in una struttura ad albero. L'albero di ricerca binario, d'altra parte, è un tipo di albero binario in cui tutti i nodi nel sottoalbero sinistro sono inferiori o uguali al valore del nodo radice e quello del sottoalbero destro sono maggiori o uguali al valore del nodo radice.
3. operazione di Albero binario e albero di ricerca binaria- L'albero binario può essere qualsiasi cosa che abbia due figli e un genitore. Le operazioni comuni che possono essere eseguite su un albero binario sono l'inserimento, la cancellazione e l'attraversamento. Gli alberi binari di ricerca sono più di alberi binari ordinati che consentono una ricerca, inserimento e cancellazione rapida ed efficiente degli articoli. A differenza degli alberi binari, gli alberi di ricerca binaria mantengono le loro chiavi ordinate, quindi la ricerca di solito implementa la ricerca binaria per le operazioni.
4. tipi di Albero binario e albero di ricerca binaria- Esistono diversi tipi di alberi binari, tra cui "Albero binario completo", "Albero binario completo", "Albero binario perfetto" e "Albero binario esteso". Alcuni tipi comuni di alberi di ricerca binari includono alberi a T, alberi AVL, alberi Splay, alberi Tango, alberi rosso-neri, ecc..

Albero binario vs Albero di ricerca binario: grafico di confronto

Riepilogo dell'albero binario e dell'albero di ricerca binaria

Mentre entrambi simulano una struttura ad albero gerarchica che rappresenta una collezione di nodi con ciascun nodo che rappresenta un valore, sono piuttosto diversi l'uno dall'altro in termini di come possono essere implementati e utilizzati. Un albero binario segue una semplice regola che ogni nodo genitore non ha più di due nodi figli, mentre un albero di ricerca binario è solo una variante dell'albero binario che segue un ordine relativo a come i nodi dovrebbero essere organizzati in un albero.