Tutto ciò che è necessario sapere sulle strutture dati dell'albero

Gli alberi sono così belli. Un disegno che ho fatto quando ero un ragazzino.

Quando impari per la prima volta a programmare, è comune apprendere gli array come la "struttura di dati principale".

Alla fine, imparerai anche le tabelle di hash. Se stai perseguendo una laurea in Informatica, devi seguire un corso sulla struttura dei dati. Imparerai anche su elenchi collegati, code e pile. Tali strutture di dati sono chiamate strutture di dati "lineari" perché hanno tutte un inizio logico e una fine logica.

Quando iniziamo a conoscere alberi e grafici, può diventare davvero confuso. Non archiviamo i dati in modo lineare. Entrambe le strutture di dati memorizzano i dati in un modo specifico.

Questo post serve per aiutarti a comprendere meglio la Struttura dei dati dell'albero e per chiarire ogni confusione che potresti avere al riguardo.

In questo articolo impareremo:

  • Che cos'è un albero
  • Esempi di alberi
  • La sua terminologia e come funziona
  • Come implementare le strutture ad albero nel codice.

Cominciamo questo viaggio di apprendimento. :)

Definizione

Quando si inizia la programmazione, è comune comprendere meglio le strutture di dati lineari rispetto a strutture di dati come alberi e grafici.

Gli alberi sono noti come una struttura di dati non lineare. Non memorizzano i dati in modo lineare. Organizzano i dati gerarchicamente.

Tuffiamoci negli esempi di vita reale!

Cosa intendo quando dico in modo gerarchico?

Immagina un albero genealogico con relazioni di tutte le generazioni: nonni, genitori, figli, fratelli, ecc. Organizziamo comunemente alberi genealogici gerarchicamente.

Il mio albero genealogico

Il disegno sopra è il mio albero genealogico. Tossico, Akikazu, Hitomi e Takemi sono i miei nonni.

Toshiaki e Juliana sono i miei genitori.

TK, Yuji, Bruno e Kaio sono i figli dei miei genitori (io e i miei fratelli).

La struttura di un'organizzazione è un altro esempio di gerarchia.

La struttura di un'azienda è un esempio di gerarchia

In HTML, il Document Object Model (DOM) funziona come un albero.

Document Object Model (DOM)

Il tag HTML contiene altri tag. Abbiamo un tag head e un body tag. Quei tag contengono elementi specifici. Il tag head ha meta e tag title. Il tag body ha elementi che vengono visualizzati nell'interfaccia utente, ad esempio h1, a, li, ecc.

Una definizione tecnica

Un albero è una raccolta di entità chiamate nodi. I nodi sono collegati da bordi. Ogni nodo contiene un valore o dati e può avere o meno un nodo figlio.

Il primo nodo dell'albero è chiamato radice. Se questo nodo radice è collegato da un altro nodo, la radice è quindi un nodo padre e il nodo collegato è un figlio.

Tutti i nodi Tree sono collegati da collegamenti chiamati edge. È una parte importante degli alberi, perché gestisce la relazione tra i nodi.

Le foglie sono gli ultimi nodi su un albero. Sono nodi senza figli. Come alberi veri, abbiamo la radice, i rami e infine le foglie.

Altri concetti importanti da comprendere sono altezza e profondità.

L'altezza di un albero è la lunghezza del percorso più lungo verso una foglia.

La profondità di un nodo è la lunghezza del percorso verso la sua radice.

Riepilogo terminologico

  • La radice è il nodo più in alto dell'albero
  • Edge è il collegamento tra due nodi
  • Il figlio è un nodo che ha un nodo padre
  • Parent è un nodo che ha un vantaggio rispetto a un nodo figlio
  • Leaf è un nodo che non ha un nodo figlio nella struttura
  • L'altezza è la lunghezza del percorso più lungo verso una foglia
  • La profondità è la lunghezza del percorso verso la radice

Alberi binari

Ora discuteremo di un tipo specifico di albero. Lo chiamiamo albero binario.

"Nell'informatica, un albero binario è una struttura di dati ad albero in cui ogni nodo ha al massimo due figli, che vengono definiti figlio sinistro e figlio destro." - Wikipedia

Quindi diamo un'occhiata a un esempio di albero binario.

Codifichiamo un albero binario

La prima cosa che dobbiamo tenere a mente quando implementiamo un albero binario è che si tratta di una raccolta di nodi. Ogni nodo ha tre attributi: value, left_child e right_child.

Come implementiamo un semplice albero binario che si inizializza con queste tre proprietà?

Diamo un'occhiata.

Ecco qui. La nostra classe di alberi binari.

Quando istanziamo un oggetto, passiamo il valore (i dati del nodo) come parametro. Guarda left_child e right_child. Entrambi sono impostati su Nessuno.

Perché?

Perché quando creiamo il nostro nodo, non ha figli. Abbiamo solo i dati del nodo.

Proviamolo:

Questo è tutto.

Possiamo passare la stringa "a" come valore al nostro nodo Albero binario. Se stampiamo il valore, left_child e right_child, possiamo vedere i valori.

Andiamo alla parte di inserimento. Cosa dobbiamo fare qui?

Implementeremo un metodo per inserire un nuovo nodo a destra e a sinistra.

Ecco le regole:

  • Se il nodo corrente non ha un figlio sinistro, creiamo solo un nuovo nodo e lo impostiamo sul figlio_coda del nodo corrente.
  • Se ha il figlio sinistro, creiamo un nuovo nodo e lo mettiamo nel posto del figlio sinistro corrente. Allocare questo nodo figlio sinistro al figlio sinistro del nuovo nodo.

Disegniamolo. :)

Ecco il codice:

Ancora una volta, se il nodo corrente non ha un figlio sinistro, creiamo semplicemente un nuovo nodo e lo impostiamo sul left_child del nodo corrente. Altrimenti creiamo un nuovo nodo e lo mettiamo nel posto dell'attuale figlio sinistro. Allocare questo nodo figlio sinistro al figlio sinistro del nuovo nodo.

E facciamo la stessa cosa per inserire un nodo figlio giusto.

Fatto. :)

Ma non del tutto. Dobbiamo ancora testarlo.

Costruiamo il seguente albero:

Per riassumere l'illustrazione di questo albero:

  • un nodo sarà la radice del nostro albero binario
  • un figlio sinistro è nodo b
  • un figlio giusto è il nodo c
  • b il figlio destro è il nodo d (il nodo b non ha un figlio sinistro)
  • c figlio secondario è e nodo
  • c figlio giusto è f nodo
  • entrambi i nodi e e non hanno figli

Quindi ecco il codice per l'albero:

L'inserimento è fatto.

Ora dobbiamo pensare all'attraversamento degli alberi.

Abbiamo due opzioni qui: Ricerca approfondita (DFS) e Ricerca approfondita (BFS).

  • DFS “è un algoritmo per attraversare o cercare la struttura dei dati dell'albero. Uno inizia dalla radice ed esplora il più possibile lungo ogni ramo prima di tornare indietro. ”- Wikipedia
  • BFS “è un algoritmo per attraversare o cercare la struttura dei dati dell'albero. Inizia dalla radice dell'albero ed esplora prima i nodi vicini, prima di passare ai vicini di livello successivo. ”- Wikipedia

Quindi tuffiamoci in ogni tipo di attraversamento di alberi.

Ricerca approfondita (DFS)

DFS esplora un percorso fino a una foglia prima di tornare indietro ed esplorare un altro percorso. Diamo un'occhiata a un esempio con questo tipo di attraversamento.

Il risultato per questo algoritmo sarà 1–2–3–4–5–6–7.

Perché?

Analizziamolo.

  1. Inizia dalla radice (1). Stampalo.

2. Vai al bambino sinistro (2). Stampalo.

3. Quindi vai al bambino sinistro (3). Stampalo. (Questo nodo non ha figli)

4. Torna indietro e vai al bambino giusto (4). Stampalo. (Questo nodo non ha figli)

5. Tornare indietro al nodo principale e passare al figlio giusto (5). Stampalo.

6. Vai al bambino sinistro (6). Stampalo. (Questo nodo non ha figli)

7. Torna indietro e vai al bambino giusto (7). Stampalo. (Questo nodo non ha figli)

8. Fatto.

Quando andiamo in profondità alla foglia e al backtrack, questo si chiama algoritmo DFS.

Ora che abbiamo familiarità con questo algoritmo trasversale, discuteremo i tipi di DFS: pre-ordine, in ordine e post-ordine.

Preordinare

Questo è esattamente ciò che abbiamo fatto nell'esempio sopra.

  1. Stampa il valore del nodo.
  2. Vai al bambino sinistro e stampalo. Questo è se, e solo se, ha un figlio sinistro.
  3. Vai al bambino giusto e stampalo. Questo è se, e solo se, ha un figlio giusto.

In ordine

Il risultato dell'algoritmo in ordine per questo esempio dell'albero è 3–2–4–1–6–5–7.

Il primo a sinistra, il secondo in mezzo e l'ultimo a destra.

Ora codifichiamolo.

  1. Vai al bambino sinistro e stampalo. Questo è se, e solo se, ha un figlio sinistro.
  2. Stampa il valore del nodo
  3. Vai al bambino giusto e stampalo. Questo è se, e solo se, ha un figlio giusto.

Post-ordine

Il risultato dell'algoritmo di ordine postale per questo esempio dell'albero è 3–4–2–6–7–5–1.

Il primo a sinistra, il secondo a destra e l'ultimo al centro.

Codifichiamo questo.

  1. Vai al bambino sinistro e stampalo. Questo è se, e solo se, ha un figlio sinistro.
  2. Vai al bambino giusto e stampalo. Questo è se, e solo se, ha un figlio giusto.
  3. Stampa il valore del nodo

Ricerca per primo (BFS)

L'algoritmo BFS attraversa il livello dell'albero per livello e profondità per profondità.

Ecco un esempio che aiuta a spiegare meglio questo algoritmo:

Quindi attraversiamo livello per livello. In questo esempio, il risultato è 1–2–5–3–4–6–7.

  • Livello / Profondità 0: solo nodo con valore 1
  • Livello / Profondità 1: nodi con valori 2 e 5
  • Livello / Profondità 2: nodi con valori 3, 4, 6 e 7

Ora codifichiamolo.

Per implementare un algoritmo BFS, utilizziamo la struttura dei dati della coda per aiutare.

Come funziona?

Ecco la spiegazione.

  1. Per prima cosa aggiungi il nodo radice nella coda con il metodo put.
  2. Scorrere mentre la coda non è vuota.
  3. Ottieni il primo nodo nella coda e quindi stampa il suo valore.
  4. Aggiungi entrambi i figli sinistro e destro nella coda (se il nodo corrente ha figli).
  5. Fatto. Stamperemo il valore di ciascun nodo, livello per livello, con il nostro queuehelper.

Albero di ricerca binaria

"Un albero di ricerca binaria viene talvolta chiamato alberi binari ordinati o ordinati e mantiene i suoi valori in ordine, in modo che la ricerca e altre operazioni possano utilizzare il principio della ricerca binaria" - Wikipedia

Una proprietà importante di un albero di ricerca binaria è che il valore di un nodo dell'albero di ricerca binario è maggiore del valore della prole del figlio sinistro, ma inferiore al valore della prole del figlio destro. "

Ecco un dettaglio dell'illustrazione sopra:

  • A è invertito. Il sottotree 7–5–8–6 deve essere sul lato destro e il sottotree 2–1–3 deve essere sulla sinistra.
  • B è l'unica opzione corretta. Soddisfa la proprietà dell'albero di ricerca binaria.
  • C ha un problema: il nodo con il valore 4. Deve trovarsi sul lato sinistro della radice perché è più piccolo di 5.

Codifichiamo un albero di ricerca binario!

Ora è il momento di programmare!

Cosa vedremo qui? Inseriremo nuovi nodi, cercheremo un valore, elimineremo i nodi e il bilancio dell'albero.

Iniziamo.

Inserimento: aggiunta di nuovi nodi al nostro albero

Immagina di avere un albero vuoto e di aggiungere nuovi nodi con i seguenti valori in questo ordine: 50, 76, 21, 4, 32, 100, 64, 52.

La prima cosa che dobbiamo sapere è se 50 è la radice del nostro albero.

Ora possiamo iniziare a inserire nodo per nodo.

  • 76 è maggiore di 50, quindi inserire 76 sul lato destro.
  • 21 è inferiore a 50, quindi inserire 21 sul lato sinistro.
  • 4 è minore di 50. Il nodo con valore 50 ha un figlio sinistro 21. Poiché 4 è minore di 21, inserirlo nella parte sinistra di questo nodo.
  • 32 è minore di 50. Il nodo con valore 50 ha un figlio sinistro 21. Poiché 32 è maggiore di 21, inserire 32 sul lato destro di questo nodo.
  • 100 è maggiore di 50. Il nodo con valore 50 ha un figlio destro 76. Poiché 100 è maggiore di 76, inserire 100 sul lato destro di questo nodo.
  • 64 è maggiore di 50. Il nodo con valore 50 ha un figlio destro 76. Poiché 64 è più piccolo di 76, inserire 64 sul lato sinistro di questo nodo.
  • 52 è maggiore di 50. Il nodo con valore 50 ha un figlio destro 76. Poiché 52 è più piccolo di 76, il nodo con valore 76 ha un figlio sinistro 64. 52 è più piccolo di 64, quindi inserire 54 sul lato sinistro di questo nodo.

Noti uno schema qui?

Analizziamolo.

  1. Il nuovo valore del nodo è maggiore o minore del nodo corrente?
  2. Se il valore del nuovo nodo è maggiore del nodo corrente, passare alla sottostruttura destra. Se il nodo corrente non ha un figlio giusto, inseriscilo lì, oppure torna indietro al passaggio 1.
  3. Se il valore del nuovo nodo è inferiore al nodo corrente, passare alla sottostruttura sinistra. Se il nodo corrente non ha un figlio sinistro, inseriscilo lì, oppure torna indietro al passaggio 1.
  4. Non abbiamo gestito casi speciali qui. Quando il valore di un nuovo nodo è uguale al valore corrente del nodo, utilizzare la regola numero 3. Considerare di inserire valori uguali sul lato sinistro della sottostruttura.

Ora codifichiamolo.

Sembra molto semplice

La parte potente di questo algoritmo è la parte ricorsiva, che si trova sulla riga 9 e sulla riga 13. Entrambe le righe di codice chiamano il metodo insert_node e lo usano rispettivamente per i suoi figli sinistro e destro. Le righe 11 e 15 sono quelle che eseguono l'inserimento per ogni bambino.

Cerchiamo il valore del nodo ... O no ...

L'algoritmo che costruiremo ora riguarda le ricerche. Per un dato valore (numero intero), diremo se il nostro albero di ricerca binario ha o non ha quel valore.

Un elemento importante da notare è come abbiamo definito l'algoritmo di inserimento dell'albero. Per prima cosa abbiamo il nostro nodo principale. Tutti i nodi di sottostruttura a sinistra avranno valori più piccoli rispetto al nodo radice. E tutti i nodi di sottostruttura giusti avranno valori maggiori del nodo radice.

Diamo un'occhiata a un esempio.

Immagina di avere questo albero.

Ora vogliamo sapere se abbiamo un nodo basato sul valore 52.

Analizziamolo.

  1. Iniziamo con il nodo radice come nodo corrente. Il valore dato è inferiore al valore del nodo corrente? Se sì, lo cercheremo nella sottostruttura sinistra.
  2. Il valore dato è maggiore del valore del nodo corrente? Se sì, lo cercheremo nella sottostruttura giusta.
  3. Se le regole n. 1 e n. 2 sono entrambe false, possiamo confrontare il valore del nodo corrente e il valore dato se sono uguali. Se il confronto ritorna vero, allora possiamo dire: "Sì! Il nostro albero ha il valore dato ", altrimenti, diciamo," Nooo, non è così. "

Ora codifichiamolo.

Analizziamo il codice:

  • Le righe 8 e 9 rientrano nella regola n. 1.
  • Le righe 10 e 11 rientrano nella regola n. 2.
  • La riga 13 rientra nella regola 3.

Come lo testiamo?

Creiamo il nostro albero di ricerca binario inizializzando il nodo principale con il valore 15.

E ora inseriremo molti nuovi nodi.

Per ogni nodo inserito, verificheremo se il nostro metodo find_node funziona davvero.

Sì, funziona per questi valori dati! Testiamo un valore che non esiste nella nostra struttura di ricerca binaria.

O si.

La nostra ricerca è fatta.

Cancellazione: rimozione e organizzazione

L'eliminazione è un algoritmo più complesso perché dobbiamo gestire casi diversi. Per un dato valore, dobbiamo rimuovere il nodo con questo valore. Immagina i seguenti scenari per questo nodo: non ha figli, ha un figlio singolo o ha due figli.

  • Scenario n. 1: un nodo senza figli (nodo foglia).

Se il nodo che vogliamo eliminare non ha figli, lo eliminiamo semplicemente. L'algoritmo non ha bisogno di riorganizzare l'albero.

  • Scenario n. 2: un nodo con un solo figlio (figlio sinistro o destro).

In questo caso, il nostro algoritmo deve fare in modo che il genitore del nodo punti al nodo figlio. Se il nodo è il figlio sinistro, facciamo in modo che il genitore del figlio sinistro punti al figlio. Se il nodo è il figlio giusto del suo genitore, facciamo in modo che il genitore del figlio giusto punti al figlio.

  • Scenario n. 3: un nodo con due figli.

Quando il nodo ha 2 figli, dobbiamo trovare il nodo con il valore minimo, a partire dal figlio giusto del nodo. Metteremo questo nodo con un valore minimo al posto del nodo che vogliamo rimuovere.

È tempo di programmare.

  1. Primo: annotare il valore dei parametri e parent. Vogliamo trovare il nodo che ha questo valore e il genitore del nodo è importante per la rimozione del nodo.
  2. Secondo: annotare il valore di ritorno. Il nostro algoritmo restituirà un valore booleano. Restituisce True se trova il nodo e lo rimuove. Altrimenti restituirà False.
  3. Dalla riga 2 alla riga 9: iniziamo a cercare il nodo che ha il valore che stiamo cercando. Se il valore è inferiore al nodevalue corrente, passiamo alla sottostruttura sinistra, in modo ricorsivo (se e solo se, il nodo corrente ha un figlio sinistro). Se il valore è maggiore, passare alla sottostruttura destra, in modo ricorsivo.
  4. Linea 10: iniziamo a pensare all'algoritmo remove.
  5. Dalla riga 11 alla riga 13: copriamo il nodo senza figli, ed è il figlio sinistro dal suo genitore. Rimuoviamo il nodo impostando il figlio sinistro del genitore su Nessuno.
  6. Linee 14 e 15: copriamo il nodo senza figli, ed è il figlio giusto dal suo genitore. Rimuoviamo il nodo impostando il figlio destro del genitore su Nessuno.
  7. Metodo del nodo chiaro: mostrerò il codice clear_node di seguito. Imposta i nodi figlio sinistro, figlio destro e il suo valore su Nessuno.
  8. Dalla riga 16 alla riga 18: copriamo il nodo con un solo figlio (figlio sinistro), ed è il figlio sinistro dal suo genitore. Impostiamo il figlio sinistro del genitore sul figlio sinistro del nodo (l'unico figlio che ha).
  9. Dalla riga 19 alla riga 21: copriamo il nodo con un solo figlio (figlio sinistro), ed è il figlio giusto dal suo genitore. Impostiamo il figlio destro del genitore sul figlio sinistro del nodo (l'unico figlio che ha).
  10. Dalla riga 22 alla riga 24: copriamo il nodo con un solo figlio (figlio destro), ed è il figlio sinistro dal suo genitore. Impostiamo il figlio sinistro del genitore sul figlio destro del nodo (l'unico figlio che ha).
  11. Dalla riga 25 alla riga 27: copriamo il nodo con un solo figlio (figlio giusto), ed è il figlio giusto dal suo genitore. Impostiamo il figlio giusto del genitore sul figlio giusto del nodo (l'unico figlio che ha).
  12. Dalla linea 28 alla linea 30: copriamo il nodo con i bambini sia a destra che a sinistra. Otteniamo il nodo con il valore più piccolo (il codice è mostrato di seguito) e lo impostiamo sul valore del nodo corrente. Termina rimuovendo il nodo più piccolo.
  13. Riga 32: se troviamo il nodo che stiamo cercando, deve restituire True. Dalla riga 11 alla riga 31, gestiamo questo caso. Quindi restituisci True e basta.
  • Per utilizzare il metodo clear_node: imposta il valore Nessuno su tutti e tre gli attributi - (valore, left_child e right_child)
  • Per usare il metodo find_minimum_value: scendi a sinistra. Se non riusciamo a trovare più nodi, abbiamo trovato il più piccolo.

Ora proviamo.

Useremo questo albero per testare il nostro algoritmo remove_node.

Rimuoviamo il nodo con il valore 8. È un nodo senza figli.

Ora rimuoviamo il nodo con il valore 17. È un nodo con un solo figlio.

Infine, rimuoveremo un nodo con due figli. Questa è la radice del nostro albero.

I test sono ora terminati. :)

È tutto per ora!

Abbiamo imparato molto qui.

Complimenti per aver finito questo contenuto denso. È davvero difficile capire il concetto che non conosciamo. Ma l'hai fatto. :)

Questo è un ulteriore passo avanti nel mio viaggio verso l'apprendimento e la padronanza di algoritmi e strutture di dati. Puoi vedere la documentazione del mio viaggio completo qui sulla mia pubblicazione Renaissance Developer.

Divertiti, continua a studiare e scrivere codice.

Spero che questo contenuto ti sia piaciuto. Sostieni il mio lavoro su Ko-Fi

Il mio Twitter e Github. ☺

Risorse addizionali

  • Introduzione alla struttura dei dati dell'albero di mycodeschool
  • Albero di Wikipedia
  • Come non essere sconcertato dagli alberi dal talentuoso Vaidehi Joshi
  • Introduzione agli alberi, conferenza del professor Jonathan Cohen
  • Introduzione agli alberi, conferenza del professor David Schmidt
  • Introduzione agli alberi, conferenza del professor Victor Adamchik
  • Alberi con Gayle Laakmann McDowell
  • Implementazione e test dell'albero binario di TK
  • Corso Coursera: Strutture dati dell'Università della California, San Diego
  • Corso Coursera: Strutture dati e performance dell'Università della California, San Diego
  • Concetti e implementazione dell'albero di ricerca binario di Paul Programming
  • Implementazione e test dell'albero di ricerca binario di TK
  • Tree Traversal da Wikipedia
  • Albero di ricerca binario Rimuovi algoritmo nodo da GeeksforGeeks
  • Albero di ricerca binario Rimuovi algoritmo nodo da Algolist
  • Imparare Python da zero a eroe