Spiegazione dei 5 tipi di albero binario nella struttura dei dati

Un albero binario è una struttura dati ad albero non lineare che contiene ogni nodo con un massimo di 2 figli. Il nome binario suggerisce il numero 2, quindi qualsiasi albero binario può avere un figlio sinistro e uno destro.

Un puntatore rappresenta un albero binario al nodo più in alto, generalmente noto come radice dell'albero. Ogni nodo in un albero binario contiene dati, un puntatore al figlio sinistro e un puntatore al figlio destro. I puntatori vengono utilizzati per implementare un albero binario. Il puntatore radice denota il primo nodo nell'albero. Per creare un albero binario, devi prima creare un nodo.

Dopo aver acquisito familiarità conl'albero binario nella struttura dei dati , è necessario conoscere anche le operazioni di base eseguite su un albero binario.È possibile eseguire funzioni come l'inserimento di un elemento, la rimozione di un elemento, la ricerca di un elemento e l'attraversamento dell'albero binario.

Qualsiasialbero binario nella struttura dei dati viene utilizzato in due modi diversi nell'informatica.In primo luogo, vengono utilizzati per accedere ai nodi in base a etichette o valori specifici collegati a ciascun nodo. In secondo luogo, vengono utilizzati come rappresentazioni di dati con una struttura ramificata rilevante.

Prima di esaminare i varitipi di albero binario , familiarizziamo con le terminologie utilizzate in un albero binario.

Nodo: contiene un valore di dati in un albero binario.

Radice: il nodo più in alto in qualsiasi albero binario è chiamato radice di un albero.

Dimensione: Indica il numero di nodi in un albero binario.

Nodo padre: un nodo in un albero binario con un figlio.

Nodo figlio: è un nodo che ha origine da un nodo genitore che si allontana dalla radice dell'albero binario.

Nodo interno: è un nodo con almeno un figlio in un albero binario.

Nodo foglia: è un nodo senza figli.In alternativa è un nodo esterno.

Profondità di un albero dei nodi: viene calcolata nel contesto di un particolare nodo.Viene indicato come il numero di spigoli da un particolare nodo alla radice.

Lunghezza del percorso interno di un albero: si riferisce alla somma dei livelli di ogni nodo interno in un albero binario.

Lunghezza del percorso esterno di un albero: è definita come la somma dei livelli di ogni nodo esterno in un albero binario.

Altezza del nodo in un albero: è il numero di spigoli da un nodo specifico al nodo foglia più profondo dell'albero binario.L'altezza della radice sarà sempre maggiore di quella degli altri nodi nell'albero binario.

Ora diamo un'occhiata ai dettagli di 5tipi di albero binario.

Tipi di albero binario

1. Albero binario completo

Questoalbero binario nella struttura dei dati è noto anche con i nomi -Albero binario corretto e Albero binario rigoroso.È uno deitipi più fondamentali di albero binario nella struttura dei dati.Un albero binario completo è definito come un albero binario in cui ogni nodo dovrebbe avere due o nessun figlio.

In alternativa è caratterizzato come un albero binario in cui ogni nodo comprende due figli tranne i nodi foglia. I nodi in cui è memorizzato l'indirizzo del nodo radice sono chiamati nodi figli della radice. Quei nodi privi di figli sono chiamati nodi foglia.

Devi percorrere tutti i nodi per verificare se un albero è un albero binario. Il codice restituirà "False" se qualsiasi nodo ha un figlio. Restituirà "True" se tutti i nodi hanno 0 o 2 figli.

Ecco le proprietà di un albero binario completo:

• Il numero di nodi foglia è uguale al numero di nodi interni + 1. Ad esempio, se il numero di nodi interni è 4, il numero di nodi foglia è uguale a 5.
• Il numero massimo di nodi e il numero di nodi in un albero binario sono uguali. È rappresentato come 2h+1 -1.
• Il numero minimo di nodi in un albero binario completo è 2h-1.
• L'altezza minima di un albero binario completo è log 2 (n+1) – 1.
• L'altezza massima di un albero binario completo è h = (n+1)/2.

2. Albero binario perfetto

Un albero binario perfetto è uno di queitipi di alberi binari in cui ogni nodo deve avere 0 o 2 figli e il livello di ogni nodo foglia deve essere lo stesso.In altre parole, gli alberi binari perfettinella struttura dati sono definiti come quegli alberi in cui tutti i nodi interni possiedono due rami e quei nodi senza rami (nodi foglia) esistono allo stesso livello.

In questo contesto, il livello di un nodo è la distanza o l'altezza dal nodo radice. Puoi considerare un albero binario perfetto come un albero binario completo in cui anche l'ultimo livello è completamente occupato.

Seguii corsi di scienza dei dationline dalle migliori università del mondo.Guadagna programmi Executive PG, programmi di certificazione avanzata o programmi master per accelerare la tua carriera.

3. Albero binario completo

Un albero binario completo è uno di quei tipi di albero binario nella struttura dei dati in cui tutti i livelli dell'albero sono completamente riempiti.L'ultimo livello dell'albero binario può o non può essere completamente riempito. Tuttavia, ogni nodo deve trovarsi nella posizione più a sinistra nell'ultimo livello del nodo. I nodi devono essere inclusi da sinistra.

Sono uno deitipi essenziali di alberi binari perché offrono il miglior rapporto tra il numero di nodi e l'altezza di un albero.

Ecco le proprietà chiave di un albero binario completo:

• Il numero massimo di nodi è 2 h+1 – 1.
• Il numero minimo di nodi è 2 h .
• L'altezza minima è log 2 (n+1) – 1.

4. Albero binario bilanciato

Negli alberi binari bilanciati, l'altezza di un albero è log 2 del numero totale di nodi. Supponiamo che l'altezza dell'albero sia he il numero totale di nodi dell'albero sia n. L'equazione per calcolare l'altezza è h = log(n). Il dislivello massimo tra un sottoalbero di destra e un sottoalbero di sinistra deve essere “1”.

La differenza può avere altri valori come 0 e -1. Questi tipi di alberi binari sono anche chiamati alberi AVL.Uno degli esempi ben noti di alberi binari bilanciati è l'albero rosso-nero.

È possibile implementare il codice seguente per eseguire un albero binario bilanciato.

classe privata Nodo {

valore int privato;

nodo privato rimasto;

diritto privato del nodo;

}

public boolean isBalanced(Nodo n) {

if (balancedtreeHeight(n) > -1)

restituisce vero;

restituire falso;

}

public int balancetreeHeight(Nodo n) {

se (n == nullo)

ritorno 0;

int h1 = balancetreeHeight(n.right);

int h2 = balancetreeHeight(n.left);

se (h1 == -1 || h2 == -1)

ritorno -1;

se (Math.abs(h1 – h2) > 1)

ritorno -1;

se (h1 > h2)

ritorno h1 + 1;

ritorno h2 + 1;

}

Dai un'occhiata ai nostri programmi di scienza dei dati negli Stati Uniti

5. Albero binario degenerato

Un albero binario degenerato è uno dei tipi meno usatidi albero binario di ricerca .È un albero binario in cui ogni nodo ha un solo figlio, cioè un figlio sinistro o destro. Nessun nodo dovrebbe avere figli sia di sinistra che di destra.

Leggi i nostri popolari articoli sulla scienza dei dati negli Stati Uniti

Conclusione

È essenziale capirecos'è l'albero binario nella struttura dei dati se si desidera utilizzarlo per varie applicazioni.L'implementazione di diverse funzioni sugli alberi binari può aiutarti a organizzare e archiviare i dati in modo efficiente.

Lo studio di più tipi di alberi binari ti aiuta a eseguire operazioni in modo più efficace nella complessità temporale. I fondamenti della scienza dei dati, inclusala struttura dei dati ad albero binario, ti aiutano a iniziare facilmente il tuo viaggio nella scienza dei dati.Successivamente, puoi lavorare su progetti avanzati di data science per migliorare le tue competenze e il tuo portfolio.

Inizia il tuo viaggio nel machine learning su upGrad

Se vuoi imparare Data Science, puoi seguire il programma di Master of Science in Data Science di upGrad . Questo corso di 24 mesi impartisce competenze come Python, Deploy ML Models, elaborazione BD utilizzando Spark, Predictive Analytics & Statistics e modelli ML supervisionati e non supervisionati. adatto a manager ambiziosi, laureati MBA, ingegneri e professionisti in vari settori.

Il completamento di questo corso ti aiuterà a lavorare come Data Engineer, Big Data Analyst, Machine Learning Engineer e Data Scientist.