Introduzione agli alberi nella struttura dei dati
Prima di comprendere i tipi di alberi nella struttura dei dati, per prima cosa studieremo gli alberi nella struttura dei dati. L'albero nel campo del computer è anche chiamato albero del mondo reale, tuttavia la differenza tra il mondo reale e l'albero del campo di calcolo è che è visualizzato come capovolto e radice su di esso e ramo da radice a foglie di albero. Tra le varie applicazioni del mondo reale, viene utilizzata la struttura dei dati dell'albero in quanto può dimostrare le relazioni tra nodi diversi con la gerarchia padre-figlio. Per questo motivo viene anche chiamata struttura gerarchica dei dati. È più popolare per semplificare e velocizzare la ricerca e l'ordinamento. È considerata una delle strutture dati più potenti e avanzate. Un albero è una rappresentazione della struttura dati non lineare. Un albero può essere mostrato utilizzando diversi tipi di dati definiti dall'utente o primitivi. È possibile utilizzare matrici, elenchi di classi connesse o altri tipi di strutture dati per implementare l'albero. È un gruppo di nodi correlati. I nodi sono collegati ai bordi per dimostrare la relazione.
Relazioni in un albero: nel diagramma sopra riportato, P è la radice dell'albero anche P è padre di Q, R e S. Q è figlio di P. Quindi Q, R e S sono fratelli. Considerando che P è nonno di A, B, C, D ed E.
Cosa sono gli alberi?
Un albero è una struttura di dati gerarchica che archivia naturalmente le informazioni in modo gerarchico. La struttura dei dati dell'albero è una delle più efficienti e mature. Sono rappresentati i nodi collegati dai bordi.
Proprietà dell'albero: ogni albero ha un nodo radice specifico. Ogni nodo dell'albero può essere attraversato da un nodo radice. Si chiama root, in quanto l'albero era l'unica radice. Ogni figlio ha un solo genitore, ma il genitore può avere molti figli.
Tipi di alberi nella struttura dei dati
Di seguito sono riportati i tipi di alberi in una struttura di dati:
1. Albero generale
Se nessun vincolo viene posto sulla gerarchia dell'albero, un albero viene chiamato albero generale. Ogni nodo può avere un numero infinito di bambini nell'albero generale. L'albero è il super set di tutti gli altri alberi.
2. Albero binario
L'albero binario è il tipo di albero in cui è possibile trovare la maggior parte dei due figli per ciascun genitore. I bambini sono conosciuti come il bambino sinistro e il bambino giusto. Questo è più popolare della maggior parte degli altri alberi. Quando alcuni vincoli e caratteristiche vengono applicati in un albero binario, ne vengono utilizzati anche altri come albero AVL, BST (albero di ricerca binario), albero RBT, ecc. Quando andremo avanti, spiegheremo tutti questi stili in dettaglio.
3. Albero di ricerca binario
Binary Search Tree (BST) è un'estensione dell'albero binario con diverse restrizioni opzionali. Il valore figlio sinistro di un nodo in BST dovrebbe essere minore o uguale al valore padre e il valore figlio destro dovrebbe essere sempre maggiore o uguale al valore padre. Questa proprietà dell'albero di ricerca binaria lo rende ideale per le operazioni di ricerca poiché possiamo determinare con precisione su ciascun nodo se il valore si trova nel sotto-albero sinistro o destro. Questo è il motivo per cui l'albero di ricerca è chiamato.
4. Albero AVL
L'albero AVL è un albero binario di auto-bilanciamento. A nome degli inventori Adelson-Velshi e Landis, viene dato il nome AVL. Questo è stato il primo albero che si è bilanciato dinamicamente. Un fattore di bilanciamento viene allocato per ciascun nodo dell'albero AVL, in base al fatto che l'albero sia bilanciato o meno. L'altezza dei bambini del nodo è al massimo 1. Vite AVL. Nell'albero AVL, il fattore di equilibrio corretto è 1, 0 e -1. Se l'albero ha un nuovo nodo, verrà ruotato per garantire che l'albero sia bilanciato. Verrà quindi ruotato. Operazioni comuni come visualizzazione, inserimento e rimozione richiedono tempo O (log n) nella struttura ad albero AVL. Viene applicato principalmente quando si lavora con le operazioni di ricerca.
5. Albero rosso-nero
Un altro tipo di albero con bilanciamento automatico è rosso-nero. Il nome rosso-nero è dato perché l'albero rosso-nero ha rosso o nero dipinto su ciascun nodo in base alle proprietà dell'albero rosso-nero. Mantiene l'equilibrio della foresta. Anche se questo albero non è un albero completamente bilanciato, l'operazione di ricerca richiede solo tempo O (log n). Quando i nuovi nodi vengono aggiunti nell'albero rosso-nero, i nodi verranno nuovamente ruotati per mantenere le proprietà dell'albero rosso-nero.
6. Albero di N-ary
Il numero massimo di figli in questo tipo di albero che può avere un nodo è N. Un albero binario è un albero di due anni, come al massimo 2 bambini in ogni nodo di albero binario. Un albero N-ary completo è un albero in cui i bambini di un nodo sono 0 o N.
Vantaggi dell'albero
Ora capiremo i vantaggi di Tree:
- L'albero si riflette nelle connessioni strutturali dei dati.
- L'albero viene utilizzato per la gerarchia.
- Offre un'efficace procedura di ricerca e inserimento.
- Gli alberi sono flessibili. Ciò consente di spostare i sottotitoli con il minimo sforzo.
Conclusione - Tipi di alberi nella struttura dei dati
Quindi, in questo articolo, abbiamo visto cos'è la struttura ad albero, quali sono i diversi tipi di alberi nella struttura dei dati e i suoi vantaggi. Spero che tu abbia avuto un'idea di alcuni degli alberi comuni nella struttura dei dati.
Articoli consigliati
Questa è una guida ai tipi di alberi nella struttura dei dati. Qui discutiamo di quali siano gli alberi, 6 tipi di alberi nella struttura dei dati, con vantaggi. Puoi anche consultare i nostri altri articoli correlati per saperne di più -
- Pipeline di dati AWS
- Oracle Data Warehousing
- Database multidimensionale
- Struttura dei dati Domande di intervista Java