Albero binario e albero di ricerca binario: differenza tra albero binario e albero di ricerca binario

introduzione

L'ordinamento è il processo di organizzazione dei dati in un ordine sistematico in modo che possano essere analizzati in modo più efficace. Il processo di identificazione di un particolare record è chiamato ricerca. Se i dati sono ordinati correttamente in un ordine particolare, la ricerca diventa un'attività facile ed efficiente. Questo articolo tratta di una delle più importanti strutture di dati non lineari, ovvero gli alberi.

Gli alberi vengono utilizzati principalmente per rappresentare i dati dimostrando una relazione gerarchica tra gli elementi. Ad esempio, sommario, albero genealogico. Tecnicamente, un albero può essere definito come un insieme finito 'T' di uno o più nodi tale che un nodo è assegnato come radice dell'albero e gli altri nodi sono divisi in n>=0 insiemi disgiunti T1, T2, T3, T4…. Tn e sono chiamati come sottoalberi o figli di quel nodo radice.

Cos'è un albero binario?

Un albero binario è una struttura dati non lineare in cui un nodo può avere 0, 1 o 2 nodi. Ogni nodo nell'albero binario è definito come nodo padre o come nodo figlio. Il nodo più in alto dell'albero binario è indicato come nodo radice. Ogni nodo padre può avere al massimo 2 nodi figlio che sono il nodo figlio sinistro e il nodo figlio destro.

Un nodo in un albero binario ha tre campi:

1. Elemento dati: memorizza il valore dei dati che deve essere archiviato dal nodo.
2. Puntatore al figlio sinistro: memorizza il riferimento (o l'indirizzo) al nodo figlio sinistro.
3. Puntatore al figlio di destra – Memorizza il riferimento al nodo figlio di destra.

In questo modo, diversi nodi vengono combinati insieme per costruire un albero binario.

Un albero binario può essere rappresentato come:

Fonte

Dalla figura sopra, il nodo radice 2 ha due figli (o nodi figli), 7 e 5. 7 è chiamato nodo figlio sinistro e 5 è chiamato nodo figlio destro. In questo modo, ciascuno dei nodi figli funge da nodo padre per molti altri nodi e insieme rappresentano l'albero binario.

Scopri: Tipi di albero binario

Terminologie utilizzate nell'albero binario

Nodo : la rappresentazione di base di un punto terminale in un albero.

Nodo radice : il nodo più in alto di un albero binario.

Nodo padre : se un nodo è connesso a un altro nodo tramite i bordi, è noto come nodo padre. In un albero binario, un nodo padre può avere un massimo di 2 nodi figlio.

Nodo figlio : se un nodo ha un predecessore, è noto come nodo figlio.

Nodo foglia : un nodo che non ha alcun nodo figlio viene chiamato nodo foglia.

Profondità di un nodo : è la distanza dal nodo radice a quel particolare nodo la cui profondità deve essere misurata.

Altezza dell'albero : è la distanza più lunga dal nodo radice al nodo foglia.

Queste sono alcune terminologie di base di un albero binario. Con questa comprensione di base di un albero binario, passiamo a un avanzamento dell'albero binario noto come albero di ricerca binario.

Leggi anche: Algoritmo di ricerca binaria: funzione, vantaggi, complessità temporale e spaziale

Che cos'è un albero di ricerca binario

Come suggerisce il nome, un albero di ricerca binaria o BST è un albero utilizzato per ordinare, recuperare e cercare i dati. È anche un tipo di struttura dati non lineare in cui i nodi sono disposti in un ordine particolare. Quindi, è anche chiamato " Albero binario ordinato ". Ha le seguenti proprietà:

• Il sottoalbero sinistro di un nodo ha nodi che sono solo minori della chiave di quel nodo.
• Il sottoalbero destro di un nodo ha nodi che sono solo maggiori della chiave di quel nodo.
• Ogni nodo ha chiavi distinte e i duplicati non sono consentiti nell'albero di ricerca binaria.
• Anche il sottoalbero sinistro e destro deve essere un albero di ricerca binario.

Visualizziamo questo concetto per avere una chiara comprensione degli alberi di ricerca binari.

Fonte

Nella figura sopra, vediamo che il valore del nodo radice è 8. Con un ulteriore esame, si osserva che tutti i valori nel sottoalbero di sinistra sono inferiori al valore del nodo radice e tutti i valori nel sottoalbero di destra hanno valori maggiori del nodo radice. Inoltre, si nota che ogni valore nell'albero di ricerca binaria è unico e non ci sono duplicati. Pertanto, le proprietà dell'albero di ricerca binario sopra indicate sono verificate.

In ancora un altro esempio, vediamo che sebbene i sottoalberi sinistro e destro siano alberi di ricerca binari con valori univoci in tutto l'albero. Il valore del nodo foglia nel sottoalbero di sinistra è 12, che è maggiore del valore del nodo radice che è 12. Pertanto, questo non soddisfa la proprietà del BST e quindi non è un albero di ricerca binario.

Operazione di ricerca in un BST –

Considera un albero di ricerca binario con i valori indicati di seguito. Cerchiamo di capire come viene eseguita l'operazione di ricerca per ottenere 9 dall'albero di ricerca binaria.

Fonte

Per eseguire la ricerca binaria, disporremo inizialmente tutti gli interi in un array ordinato. Questo è chiamato come spazio di ricerca. Questo spazio di ricerca è costituito da due puntatori, chiamati come puntatori di inizio e fine. L'array dell'albero di ricerca binario sopra indicato è rappresentato come:

Il primo passo è calcolare il valore medio dell'array e confrontarlo con il valore da cercare, 9 nel nostro caso. Questo viene fatto calcolando n/2, dove n è il numero totale di elementi nell'array (BST) ed è 6. Pertanto, il 3 ° elemento è l'elemento centrale che è 5.

Ora che l'elemento centrale è confrontato con 9 e poiché non è uguale (maggiore), l'operazione di ricerca verrà eseguita sull'array di destra. In questo modo l'operazione di ricerca si riduce alla metà, come mostrato di seguito:

Nel passaggio successivo, l'elemento centrale viene calcolato e risulta essere 9, che corrisponde al nostro elemento da cercare.

Albero binario vs albero di ricerca binario –

Ora che abbiamo una conoscenza di base sia dell'albero binario che degli alberi di ricerca binari, riassumiamo rapidamente alcune delle differenze tra entrambi.

Conclusione

Pertanto, deduciamo che sebbene sia l'albero binario che l'albero di ricerca binario abbiano una struttura gerarchica comune con una raccolta di nodi, presentano diverse differenze nella loro applicazione. Un albero binario è una struttura di base con una semplice regola che nessun genitore deve avere più di 2 figli mentre l'albero binario di ricerca è una variante dell'albero binario che segue un particolare ordine con cui i nodi dovrebbero essere organizzati.

Se sei curioso di conoscere l'albero binario e l'albero di ricerca binario, dai un'occhiata al diploma PG in Data Science di IIIT-B e upGrad, creato per i professionisti che lavorano e offre oltre 10 casi di studio e progetti, workshop pratici, tutoraggio con l'industria esperti, 1 contro 1 con mentori del settore, oltre 400 ore di apprendimento e assistenza al lavoro con le migliori aziende.

Impara i corsi di scienza dei dati online dalle migliori università del mondo. Guadagna programmi Executive PG, programmi di certificazione avanzati o programmi di master per accelerare la tua carriera.