Differenza chiave: albero binario e albero di ricerca binario
Una struttura dati è un modo sistematico di organizzare i dati per utilizzarli in modo efficiente. La disposizione dei dati utilizzando la struttura dei dati dovrebbe ridurre il tempo di esecuzione o il tempo di esecuzione. Inoltre, la struttura dei dati dovrebbe richiedere una quantità minima di memoria. A volte i dati possono essere organizzati in una struttura ad albero. Un albero rappresenta un nodo connesso da archi. Il nodo più in alto è la radice. Ogni nodo può avere un massimo di due nodi. Sono conosciuti come nodi figlio. Il nodo a sinistra del nodo padre è il nodo figlio sinistro mentre il nodo a destra del nodo padre è il nodo destro. L'albero binario e l'albero di ricerca binario sono due strutture di dati ad albero. Un albero binario è un tipo di struttura dati in cui ogni nodo padre può avere al massimo due nodi figlio. L'albero di ricerca binario è un albero binario in cui il figlio di sinistra contiene solo nodi con valori inferiori o uguali al nodo padre e in cui il figlio di destra contiene solo nodi con valori maggiori del nodo padre. Questa è la differenza fondamentale. A differenza delle strutture dati come gli array, l'albero binario e l'albero di ricerca binario non hanno un limite superiore per memorizzare i dati.
Cos'è l'albero binario?
Quando si organizzano i dati in una struttura ad albero, il nodo in cima all'albero è noto come nodo radice. Ci può essere solo una radice per l'intero albero. Qualsiasi nodo eccetto il nodo radice ha un bordo verso l' alto fino a un nodo. Si chiama nodo padre. Il nodo sotto il codice padre è chiamato nodo figlio. Ogni nodo padre può avere un massimo di due nodi figlio. Sono indicati come nodo figlio sinistro e nodo figlio destro. Un nodo senza alcun nodo figlio è chiamato nodo foglia. Non esiste un modo specifico per organizzare i dati nell'albero binario. C'è un percorso dal nodo radice a ciascun nodo.
Figura 01: Esempio di albero binario
Sopra c'è un esempio di albero binario. L'elemento 2, in cima all'albero, è la radice. Ogni nodo ha un massimo di due nodi. Se un albero contiene dei loop o se un nodo contiene più di due nodi, non può essere classificato come un albero binario. Per passare da un nodo all' altro, c'è sempre un percorso. I nodi figlio del nodo radice 2 sono 7 e 5. È anche possibile che un nodo non abbia nodi. Ma ogni nodo non può avere più di due nodi. L'elemento destro della radice è 5. Quell'elemento 5 è il nodo padre per il nodo figlio 9. I nodi 4 e 11 non hanno elementi figlio. Pertanto, sono nodi foglia.
L'albero binario viene utilizzato per memorizzare i dati in ordine gerarchico. È simile alla struttura dei file del computer. La struttura dei dati come un array può memorizzare una quantità specifica di dati. Ma in un albero binario non c'è limite massimo al numero di nodi.
Cos'è l'albero di ricerca binaria?
Un albero di ricerca binario è una struttura di dati ad albero binario. Simile a un albero binario, anche l'albero di ricerca binario può avere due nodi. Qualsiasi nodo eccetto il nodo radice ha un bordo verso l' alto fino a un nodo. Si chiama nodo padre. Il nodo al di sotto di un dato connesso dal suo bordo verso il basso è chiamato nodo figlio. Un nodo senza alcun nodo figlio è chiamato nodo foglia. Ogni nodo padre può avere un massimo di due nodi. Esistono nodi figlio che fanno riferimento a un nodo figlio sinistro e al nodo figlio destro. L'elemento più in alto è chiamato nodo radice. Il figlio sinistro contiene solo nodi con valori inferiori o uguali al nodo padre. Il figlio destro contiene solo nodi con valori maggiori o uguali al nodo padre.
Figura 02: Esempio di albero di ricerca binario
L'elemento 8 è l'elemento più in alto. Pertanto, è il nodo radice. Se 3 è un nodo padre, allora 1 e 6 sono nodi figlio. 1 è il nodo figlio sinistro mentre 6 è il nodo figlio destro. Il figlio sinistro contiene valori inferiori o uguali al nodo padre. Quando 3 è il nodo padre, il lato sinistro dovrebbe avere un elemento minore o uguale a 3. In questo esempio, è 1. Il figlio destro contiene solo nodi con valori maggiori del nodo padre. Quando 3 è il nodo padre, il nodo figlio destro dovrebbe avere un valore maggiore di 3. In questo esempio è 6. Allo stesso modo, c'è un certo ordine per organizzare ogni elemento di dati in un albero di ricerca binario. È una struttura di dati che fornisce un modo efficiente per eseguire l'ordinamento, il recupero e la ricerca dei dati.
Quali sono le somiglianze tra l'albero binario e l'albero di ricerca binario?
- Sia l'albero binario che l'albero di ricerca binario sono strutture dati gerarchiche.
- Sia l'albero binario che l'albero di ricerca binario hanno una radice.
- Sia l'albero binario che l'albero di ricerca binario possono avere un massimo di due nodi figlio.
Qual è la differenza tra albero binario e albero di ricerca binario?
Albero binario vs albero di ricerca binario |
|
| Un albero binario è un tipo di struttura dati in cui ogni nodo padre può avere al massimo due nodi figlio. | L'albero di ricerca binario è un albero binario in cui il figlio di sinistra contiene solo nodi con valori inferiori o uguali al nodo genitore, e dove il figlio di destra contiene solo nodi con valori maggiori del nodo genitore. |
| Ordine di organizzazione dei dati | |
| Un albero binario non ha un ordine specifico per disporre gli elementi di dati. | Un albero di ricerca binario ha un ordine specifico per disporre gli elementi di dati. |
| Utilizzo | |
| Un albero binario viene utilizzato come ricerca efficiente di dati e informazioni in una struttura ad albero. | Un albero di ricerca binario viene utilizzato per inserire, eliminare e cercare i dati. |
Riepilogo – Albero binario e albero di ricerca binario
Una struttura dati è un modo per organizzare i dati. A volte i dati possono essere organizzati in una struttura ad albero. Due di loro sono l'albero binario e l'albero di ricerca binario. Questo articolo ha discusso la differenza tra l'albero binario e l'albero di ricerca binario. Un albero binario è un tipo di struttura dati in cui ogni nodo padre può avere al massimo due nodi figlio. L'albero di ricerca binario è un albero binario in cui il figlio di sinistra contiene solo nodi con valori inferiori o uguali al nodo padre e dove il figlio di destra contiene solo nodi con valori maggiori del nodo padre.
Scarica il PDF di Binary Tree vs Binary Search Tree
Puoi scaricare la versione PDF di questo articolo e usarla per scopi offline come da nota di citazione. Si prega di scaricare la versione PDF qui: Differenza tra albero binario e albero di ricerca binario
