Un Binary Search Tree è una delle varie strutture di dati che ci aiutano a organizzare e ordinare i dati. È un modo efficiente per archiviare i dati in una gerarchia ed è molto flessibile.
In questo articolo, daremo un'occhiata più da vicino a come funziona, insieme alle sue proprietà e applicazioni.
Che cos'è un albero di ricerca binario?
Un Binary Search Tree è una struttura di dati composta da nodi, simili agli elenchi collegati. Ci possono essere due tipi di nodi: un genitore e un figlio. Il nodo radice è il punto iniziale della struttura che si dirama in due nodi figli, chiamati nodo sinistro e nodo destro.
Ogni nodo può essere referenziato solo dal suo genitore e possiamo attraversare i nodi dell'albero a seconda della direzione. L'albero di ricerca binaria ha tre proprietà principali:
- Il nodo sinistro è più piccolo del suo genitore.
- Il nodo destro è maggiore del suo genitore.
- I sottoalberi sinistro e destro devono essere alberi di ricerca binari.
Un albero di ricerca binario perfetto si ottiene quando tutti i livelli sono pieni e ogni nodo ha un nodo figlio sinistro e destro.
Imparentato: Librerie di data science per Python che ogni data scientist dovrebbe utilizzare
Operazioni di base di un albero di ricerca binario
Ora che hai un'idea migliore di cosa sia un albero di ricerca binario, possiamo esaminare le sue operazioni di base di seguito.
1. Operazione di ricerca
La ricerca ci permette di individuare un particolare valore presente nell'albero. Possiamo utilizzare due tipi di ricerche: ricerca in ampiezza (BFS) e ricerca in profondità (DFS). La ricerca in ampiezza è un algoritmo di ricerca che inizia dal nodo radice e attraversa orizzontalmente, da un lato all'altro, finché non viene trovato l'obiettivo. Ogni nodo viene visitato una volta durante questa ricerca.
La ricerca in profondità, d'altra parte, attraversa l'albero verticalmente, partendo dal nodo radice e scendendo lungo un singolo ramo. Se l'obiettivo viene trovato, l'operazione termina. Ma se no, e cerca gli altri nodi.
2. Inserimento operazione
L'operazione di inserimento utilizza l'operazione di ricerca per determinare la posizione in cui deve essere inserito il nuovo nodo. Il processo inizia dal nodo radice e la ricerca inizia fino al raggiungimento della destinazione. Ci sono tre casi da considerare con l'inserimento.
- Caso 1: quando non esiste alcun nodo. Il nodo da inserire diventerà il nodo radice.
- Caso 2: Non ci sono bambini. In questo caso, il nodo verrà confrontato con il nodo radice. Se è più grande, diventerà il figlio giusto; altrimenti, diventerà il figlio sinistro.
- Caso 3: quando sono presenti la radice e i suoi figli. Il nuovo nodo verrà confrontato con ciascun nodo sul suo percorso per determinare quale nodo visiterà successivamente. Se il nodo è maggiore del nodo radice, attraverserà il sottoalbero destro oppure il sinistro. Allo stesso modo, vengono effettuati confronti su ciascun livello per determinare se andrà a destra oa sinistra fino a quando non arriverà a destinazione.
3. Elimina operazione
L'operazione di eliminazione viene utilizzata per rimuovere un particolare nodo all'interno dell'albero. L'eliminazione è considerata complicata poiché dopo aver rimosso un nodo, l'albero deve essere riorganizzato di conseguenza. Ci sono tre casi principali da considerare:
- Caso 1: Eliminazione di un nodo foglia. Un nodo foglia è un nodo senza figli. Questo è il più facile da rimuovere in quanto non influisce su nessun altro nodo; attraversiamo semplicemente l'albero finché non lo raggiungiamo e lo cancelliamo.
- Caso 2: Eliminazione di un nodo con un figlio. L'eliminazione di un genitore con un nodo farà sì che il figlio prenda la sua posizione e tutti i nodi successivi saliranno di un livello. Non ci saranno cambiamenti nella struttura dei sottoalberi.
- Caso 3: eliminazione di un nodo con due figli. Quando dobbiamo rimuovere un nodo con due figli, dobbiamo prima trovare un nodo successivo che possa prendere la sua posizione. Due nodi possono sostituire il nodo rimosso, il successore o il predecessore in ordine. Il successore inordine è il figlio più a sinistra del sottoalbero destro e il predecessore in ordine è il figlio più a destra del sottoalbero sinistro. Copiamo i contenuti del successore/predecessore sul nodo ed eliminiamo il successore/predecessore inordine.
Imparentato: Come costruire strutture dati con classi JavaScript ES6
Come attraversare un albero di ricerca binario
L'attraversamento è il processo attraverso il quale navighiamo in un albero di ricerca binario. Viene eseguito per individuare un elemento specifico o per stampare un contorno dell'albero. Partiamo sempre dal nodo radice e dobbiamo seguire i bordi per arrivare agli altri nodi. Ogni nodo dovrebbe essere considerato un sottoalbero e il processo viene ripetuto finché non vengono visitati tutti i nodi.
- Attraversamento in ordine: L'attraversamento in ordine produrrà una mappa in ordine crescente. Con questo metodo, iniziamo dal sottoalbero sinistro e proseguiamo fino alla radice e al sottoalbero destro.
- Pre-ordine di attraversamento: In questo metodo, viene visitato per primo il nodo radice, seguito dal sottoalbero sinistro e dal sottoalbero destro.
- Attraversamento Post-Ordine: Questo attraversamento comporta la visita del nodo radice per ultimo. Iniziamo dal sottoalbero sinistro, poi dal sottoalbero destro e infine dal nodo radice.
Applicazioni del mondo reale
Quindi, come utilizziamo gli algoritmi dell'albero di ricerca binario? Come si può supporre, sono estremamente efficienti nella ricerca e nell'ordinamento. La più grande forza degli alberi binari è la loro struttura organizzata. Consente di eseguire la ricerca a velocità notevoli dimezzando la quantità di dati che dobbiamo analizzare per passaggio.
Gli alberi di ricerca binari ci consentono di mantenere in modo efficiente un set di dati che cambia dinamicamente in una forma organizzata. Per le applicazioni che hanno dati inseriti e rimossi frequentemente, sono molto utili. I motori dei videogiochi utilizzano un algoritmo basato su alberi noto come partizione spaziale binaria per aiutare a rendere ordinati gli oggetti. Microsoft Excel e la maggior parte dei software per fogli di calcolo utilizzano alberi binari come struttura dati di base.
Potresti essere sorpreso di sapere che il codice Morse utilizza un albero di ricerca binario per codificare i dati. Un altro motivo importante per cui gli alberi di ricerca binaria sono così utili sono le loro molteplici varianti. La loro flessibilità ha portato alla creazione di numerose varianti per risolvere ogni tipo di problema. Se usati correttamente, gli alberi di ricerca binari sono una grande risorsa.
Alberi di ricerca binari: il punto di partenza perfetto
Uno dei modi principali per valutare l'esperienza di un ingegnere è attraverso la sua conoscenza e applicazione delle strutture dati. Le strutture di dati sono utili e possono aiutare a creare un sistema più efficiente. Gli alberi di ricerca binari sono un'ottima introduzione alle strutture dati per qualsiasi sviluppatore alle prime armi.
Vuoi capire gli array JavaScript ma non riesci a fare i conti con loro? Controlla i nostri esempi di array JavaScript per assistenza.
Leggi Avanti
- Programmazione
- Programmazione
- Strumenti di programmazione
Maxwell è uno sviluppatore di software che lavora come scrittore nel suo tempo libero. Un appassionato di tecnologia che ama dilettarsi nel mondo dell'intelligenza artificiale. Quando non è impegnato con il suo lavoro, è fuori a leggere oa giocare ai videogiochi.
Iscriviti alla nostra Newsletter
Iscriviti alla nostra newsletter per suggerimenti tecnici, recensioni, ebook gratuiti e offerte esclusive!
Clicca qui per iscriverti
