Albero binario nella struttura dei dati: proprietà, tipi, rappresentazione e vantaggi

Tra i diversi tipi di strutture dati ci sono alberi binari che hanno più usi rispetto alla maggior parte degli altri tipi. Le loro applicazioni più importanti includono programmazione peer-to-peer, ricerca, crittografia, router di rete con larghezza di banda maggiore rispetto ad altri e videogiochi 3D. Discuteremo ora in dettaglio quali sono gli alberi binari nella scienza dei dati, quali sono i loro tipi e come vengono rappresentati.

Cosa sono gli alberi binari?

Se hai già lavorato su alberi normali o ne conosci le basi, sapresti che non ci sono restrizioni quando si tratta del numero di bambini che nodi diversi possono avere in questi alberi. Gli alberi binari sono leggermente diversi in questo senso. Ogni genitore o nodo negli alberi binari può avere un massimo di solo due figli.

Tutti i nodi in un albero binario hanno tre componenti principali:

• un elemento dati
• un giusto riferimento
• un riferimento sinistro

Il nodo che si trova in cima all'albero viene chiamato nodo radice. I nodi principali sono quelli che hanno figli. I nodi figlio e i nodi padre sono collegati tra loro tramite riferimenti. I nodi che non hanno figli sono indicati come nodi foglia.

È chiaramente evidente che i nodi negli alberi binari possono avere un figlio, due figli o nessun figlio. Gli alberi binari non sono strutture di dati lineari come code, array, stack ed elenchi collegati. Sono invece strutture di dati gerarchiche.

Dai un'occhiata a: Idee per progetti di scienza dei dati per principianti

Proprietà importanti dei nodi negli alberi binari

Una migliore comprensione di queste proprietà ti aiuterà a sfruttare al meglio questa discussione sugli alberi binari. La profondità di diversi nodi è definita come il numero di nodi che esistono lungo il percorso che collega la radice a un particolare nodo. Ecco perché la profondità del nodo radice è 0. D'altra parte, l'altezza di diversi nodi in un albero binario è il numero di nodi che si trovano nel percorso che collega un particolare nodo con il nodo radice. Ecco perché l'altezza dei nodi foglia è 0.

Come puoi vedere chiaramente, la profondità di un nodo si misura partendo dal nodo radice e poi scendendo per raggiungere quel nodo. D'altra parte, quando si tratta di calcolare l'altezza, partiamo dal nodo in questione e poi ci spostiamo verso il nodo radice. Entrambe le volte, iniziamo da 0. Ci sono persone che misurano anche altezza e profondità da 1 e non da 0, il che non è sbagliato ed è proprio ciò che preferiscono le persone diverse.

Ora la profondità massima di un nodo è definita come la profondità di un albero binario. Allo stesso modo, l'altezza massima di un nodo è definita come l'altezza di un albero binario. Quindi l'altezza e la profondità di un albero binario sono sempre le stesse.

Ulteriori informazioni: Strutture dati e algoritmi in Python

Che cos'è un albero di ricerca binario?

Un albero binario di ricerca è il più comune di tutti gli altri tipi di albero binario. È un albero binario specializzato che viene fornito con proprietà diverse e più utili di qualsiasi altra forma di albero binario. Che cos'è esattamente un albero di ricerca binario o BST? Proprio come suggerisce il nome, un albero di ricerca binario viene utilizzato per cercare i dati nell'albero.

Un BST viene fornito con proprietà che gli consentono di facilitare ricerche efficienti. Un BST è un albero binario che ha la chiave del nodo che è rispettivamente più piccola e maggiore dei nodi nel sottoalbero di destra e dei nodi nel sottoalbero di sinistra.

Rappresentazione di alberi binari

1. Rappresentanza collegata

Gli alberi binari nella rappresentazione collegata vengono archiviati nella memoria come elenchi collegati. Questi elenchi hanno nodi che non sono archiviati in posizioni di memoria adiacenti o adiacenti e sono collegati tra loro tramite la relazione padre-figlio associata agli alberi.

In questa rappresentazione, ogni nodo ha tre parti diverse:

• puntatore che punta verso il nodo destro,
• puntatore che punta verso il nodo sinistro,
• elemento dati.

Questa è la rappresentazione più comune. Tutti gli alberi binari sono costituiti da un puntatore radice che punta nella direzione del nodo radice. Quando vedi un nodo radice che punta verso null o 0, dovresti sapere che hai a che fare con un albero binario vuoto. I puntatori destro e sinistro memorizzano l'indirizzo dei figli destro e sinistro dell'albero.

2. Rappresentazione sequenziale

Sebbene sia più semplice della rappresentazione collegata, la sua inefficienza lo rende una rappresentazione ad albero binario meno preferita delle due. L'inefficienza risiede nella quantità di spazio necessaria per lo stoccaggio di diversi elementi dell'albero. La rappresentazione sequenziale utilizza un array per la memorizzazione di elementi ad albero.

Il numero di nodi di un albero binario definisce la dimensione dell'array utilizzato. Il nodo radice dell'albero binario si trova nel primo indice dell'array. L'indice in cui viene archiviato un particolare nodo definirà gli indici in cui verranno archiviati i figli destro e sinistro del nodo. Un albero vuoto ha null o 0 come primo indice.

Tipi di alberi binari

1. Alberi binari completi: gli alberi binari completi sono quegli alberi binari i cui nodi hanno due figli o nessuno. In altre parole, un albero binario diventa un albero binario completo quando, a parte le foglie, tutti gli altri nodi hanno due figli.
2. Alberi binari completi: gli alberi binari completi sono quelli che hanno tutti i loro diversi livelli completamente riempiti. L'unica eccezione a questo potrebbe essere il loro ultimo livello, le cui chiavi sono prevalentemente a sinistra. Un heap binario viene spesso preso come esempio di un albero binario completo.
3. Alberi binari perfetti: gli alberi binari perfetti sono alberi binari le cui foglie sono presenti allo stesso livello e i cui nodi interni portano due figli. Un esempio comune di albero binario perfetto è un albero genealogico ancestrale.
4. Alberi binari degenerati patologici: gli alberi degenerati sono quegli alberi binari i cui nodi interni hanno un figlio. I loro livelli di prestazioni sono simili agli elenchi collegati. Ulteriori informazioni sui tipi di albero binario.

Leggi: Le sei strutture dati più comunemente utilizzate in R

Vantaggi degli alberi binari

1. Un modo ideale per seguire il modo gerarchico di archiviazione dei dati
2. Riflette le relazioni strutturali che esistono nel set di dati fornito
3. Rendi l'inserimento e l'eliminazione più veloci rispetto agli elenchi e agli array collegati
4. Un modo flessibile per conservare e spostare i dati
5. Vengono utilizzati per memorizzare quanti più nodi possibile
6. Sono più veloci degli elenchi collegati e più lenti degli array quando si tratta di accedere agli elementi

Conclusione

In questo blog, abbiamo discusso di cosa sono gli alberi binari nelle strutture dati e abbiamo parlato dei loro tipi, delle loro rappresentazioni e dei loro vantaggi. I due principali usi degli alberi sono per la ricerca e l'archiviazione dei dati, e quindi sono parte integrante dello studio della scienza dei dati e dei suoi campi correlati.

Se sei curioso di conoscere gli alberi binari nelle strutture dei dati, nella scienza dei dati, dai un'occhiata al programma Executive 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 pratici, tutoraggio con esperti del settore, 1 contro 1 con mentori del settore, oltre 400 ore di apprendimento e assistenza al lavoro con le migliori aziende.