Tutto quello che c’è da sapere sulle strutture dati ad albero

Quando si impara a codificare per la prima volta, è comune imparare gli array come “struttura dati principale”

Eventualmente, si impara anche hash tables. Se state perseguendo una laurea in informatica, dovete seguire un corso sulla struttura dei dati. Imparerete anche linked listsqueues, e stacks. Queste strutture di dati sono chiamate strutture di dati “lineari” perché hanno tutte un inizio logico e una fine logica.

Quando iniziamo ad imparare su trees e graphs, può diventare molto confuso. Non memorizziamo i dati in modo lineare. Entrambe le strutture dati memorizzano i dati in un modo specifico.

Questo post è per aiutarvi a capire meglio la struttura di dati ad albero e per chiarire qualsiasi confusione possiate avere su di essa.

In questo articolo, impareremo:

• Cos’è un albero
• Esempi di alberi
• La sua terminologia e come funziona
• Come implementare strutture ad albero nel codice.

Iniziamo questo viaggio di apprendimento. 🙂

Definizione

Quando si inizia a programmare, è comune capire meglio le strutture dati lineari rispetto a strutture dati come alberi e grafi.

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

Tuffiamoci in esempi di vita reale!

Cosa intendo quando dico in modo gerarchico?

Immaginate un albero genealogico con relazioni di tutte le generazioni: nonni, genitori, figli, fratelli, ecc. Organizziamo comunemente gli alberi genealogici in modo gerarchico.

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).

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

Il tag HTML contiene altri tag. Abbiamo un tag head e un tag body. Questi tag contengono elementi specifici. Il tag head ha i tag meta e title. Il tag body ha elementi che si mostrano nell’interfaccia utente, per esempio, h1ali, ecc.

Una definizione tecnica

Un tree è un insieme di entità chiamate nodes. I nodi sono collegati da edges. Ogni node contiene un value o data, e può avere o meno un child node .

Il first node del tree è chiamato root. Se questo root node è collegato da un altro node, il root è allora un parent node e il node collegato è un child.

Tutti i Tree nodes sono collegati da link chiamati edges. E’ una parte importante di trees, perché gestisce la relazione tra nodes.

Leaves sono gli ultimi nodes su un tree. Sono nodi senza figli. Come i veri alberi, abbiamo il rootbranches, e infine il leaves.

Altri concetti importanti da capire sono height e depth.

Il height di un tree è la lunghezza del percorso più lungo di un leaf.

Il depth di un node è la lunghezza del percorso verso il suo root.

Riassunto terminologico

• Radice è il node più alto del tree
• Bordo è il collegamento tra due nodes
• Bambino è un node che ha un parent node
• Genitore è un node che ha un edge a un child node
• Foglia è un node che non ha un child node nel tree
• Altezza è la lunghezza del percorso più lungo verso un leaf
• La profondità è la lunghezza del percorso verso il suo root

Alberi binari

Ora discuteremo un tipo specifico di tree. Lo chiamiamo ilbinary tree.

“In informatica, un albero binario è una struttura dati ad albero in cui ogni nodo ha al massimo due figli, che sono indicati come il figlio sinistro e il figlio destro.” – Wikipedia

Guardiamo quindi un esempio di un binary tree.

Codifichiamo un albero binario

La prima cosa che dobbiamo tenere a mente quando implementiamo un binary tree è che è un insieme di nodes. Ogni node ha tre attributi: valueleft_child, e right_child.

Come implementiamo un semplice binary tree che inizializza con queste tre proprietà?

Diamo un’occhiata.

class BinaryTree: def __init__(self, value): self.value = value self.left_child = None self.right_child = None

Ecco qui. Il nostro binary tree classe.

Quando istanziamo un oggetto, passiamo il value (i dati del nodo) come parametro. Guardate il left_child e il right_child. Entrambi sono impostati su None.

Perché?

Perché quando creiamo il nostro node, non ha nessun figlio. Abbiamo solo il node data.

Testiamolo:

tree = BinaryTree('a')print(tree.value) # aprint(tree.left_child) # Noneprint(tree.right_child) # None

Ecco.

Possiamo passare il stringa‘ come value al nostro Binary Tree node. Se stampiamo il valueleft_child, e right_child, possiamo vedere i valori. Cosa dobbiamo fare qui?

Implementeremo un metodo per inserire un nuovo node al right e al left.

Ecco le regole:

• Se l’attuale node non ha un left child, creiamo semplicemente un nuovo node e lo impostiamo sul left_child del nodo attuale.
• Se ha il left child, creiamo un nuovo nodo e lo mettiamo al posto dell’attuale left child. Allocate questo left child node al left child del nuovo nodo. 🙂
  

  Ecco il codice:

  Ancora una volta, se il nodo corrente non ha un left child, creiamo semplicemente un nuovo nodo e lo impostiamo sul left_child del nodo corrente. Oppure creiamo un nuovo nodo e lo mettiamo al posto dell’attuale left child. Assegniamo questo left child node al left child del nuovo nodo.

  E facciamo la stessa cosa per inserire un right child node.

  Fatto. 🙂

  Ma non del tutto. Dobbiamo ancora testarlo.

  Costruiamo il seguentetree:

  Per riassumere l’illustrazione di questo albero:

  • anode sarà il root del nostro binary Tree
  • aleft childbnode
  • aright childcnode
  • bright childdnodebnode non ha un left child)
  • cleft childenode
  • cright childfnode
  • sia e che fnodes non hanno figli

  Quindi ecco il codice per il tree:

  L’inserimento è fatto.

  Ora dobbiamo pensare al tree traversal.

  Abbiamo due opzioni: Depth-First Search (DFS) e Breadth-First Search (BFS).

  • DFS “è un algoritmo per attraversare o cercare una struttura dati ad albero. Si parte dalla radice e si esplora il più possibile lungo ogni ramo prima di fare il backtracking”. – Wikipedia
  • BFS “è un algoritmo per attraversare o cercare la struttura ad albero dei dati. Inizia alla radice dell’albero ed esplora prima i nodi vicini, prima di passare ai vicini di livello successivo”. – Wikipedia

  Perciò immergiamoci in ogni tipo di attraversamento dell’albero.

  Ricerca in profondità (DFS)

  DFS esplora un percorso fino ad una foglia prima di tornare indietro ed esplorare un altro percorso. Vediamo un esempio con questo tipo di attraversamento.

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

  Perché?

  Ripartiamo.

  1. Partiamo dal root (1). Stampalo.

  2. Vai al left child (2). Stampalo.

  3. Poi vai al left child (3). Stampatelo. (Questo node non ha figli)

  4. Tornate indietro e andate al right child (4). Stampatelo. (Questo node non ha figli)

  5. Ritornate al rootnode e andate al right child (5). Stampalo.

  6. Vai al left child (6). Stampatelo. (Questo node non ha figli)

  7. Tornate indietro e andate al right child (7). Stampatelo. (Questo node non ha figli)

  8. Fatto.

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

  Ora che abbiamo familiarità con questo algoritmo di attraversamento, discuteremo i tipi di DFS: pre-orderin-order, e post-order.

  Pre-ordine

  Questo è esattamente quello che abbiamo fatto nell’esempio precedente.

  1. Stampa il valore del node.
  2. Vai al left child e stampalo. Questo se, e solo se, ha un left child.
  3. Vai al right child e stampalo. Questo se, e solo se, ha un right child.

  In-order

  Il risultato dell’algoritmo in-order per questo tree esempio è 3-2-4-1-6-5-7.

  La sinistra per prima, la metà per seconda e la destra per ultima.

  Ora codifichiamo.

  def in_order(self): if self.left_child: self.left_child.in_order() print(self.value) if self.right_child: self.right_child.in_order()

  1. Vai al left child e stampalo. Questo se, e solo se, ha un left child.
  2. Stampa il valore del node
  3. Vai al right child e stampalo. Questo se, e solo se, ha un right child.

  Post-order

  Il risultato dell’post order algoritmo per questo tree esempio è 3-4-2-6-7-5-1.

  La sinistra per prima, la destra per seconda, e la metà per ultima.

  Codifichiamo questo.

  1. Vai al left child e stampalo. Questo se, e solo se, ha un left child.
  2. Vai al right child e stampalo. Questo se, e solo se, ha un right child.
  3. Stampa il valore del node

  Ricerca Breadth-First (BFS)

  L’algoritmo BFS attraversa il tree livello per livello e profondità per profondità.

  Ecco un esempio che aiuta a spiegare meglio questo algoritmo:

  Si attraversa livello per livello. In questo esempio, il risultato è 1-2-5-3-4-6-7.

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

  Ora codifichiamo.

  Per implementare un algoritmo BFS, usiamo la struttura dati queue come aiuto.

  Come funziona?

  Ecco la spiegazione.

  1. Prima aggiungi il rootnode nel queue con il metodo put.
  2. Iterate mentre il queue non è vuoto.
  3. Prendi il primo node nel queue, e poi stampa il suo valore.
  4. Aggiungere sia left che rightchildren in il queue (se il node corrente ha children).
  5. Fatto. Stamperemo il valore di ogni node, livello per livello, con il nostro queuehelper.

  Albero di ricerca binaria

  “Un albero di ricerca binaria è talvolta chiamato albero binario ordinato o ordinato, e mantiene i suoi valori in ordine, in modo che la ricerca e altre operazioni possano utilizzare il principio della ricerca binaria” – Wikipedia

  Un’importante proprietà di un Binary Search Tree è che il valore di un Binary Search Treenode è maggiore del valore della prole del suo left child, ma più piccolo del valore della prole del suo right child.“

  Ecco una ripartizione dell’illustrazione precedente:

  • A è invertito. Il subtree 7-5-8-6 deve essere a destra, e il subtree 2-1-3 deve essere a sinistra.
  • B è l’unica opzione corretta. Soddisfa la proprietà Binary Search Tree.
  • C ha un problema: il node con il valore 4. Deve stare a sinistra del root perché è più piccolo di 5.

  Codifichiamo un albero di ricerca binario!

  Ora è il momento di codificare!

  Cosa vedremo qui? Inseriremo nuovi nodi, cercheremo un valore, cancelleremo nodi, e il saldo del tree.

  Iniziamo.

  Inserimento: aggiungere nuovi nodi al nostro albero

  Immaginiamo di avere un tree vuoto e vogliamo aggiungere nuovi nodes con i seguenti valori in questo ordine: 50, 76, 21, 4, 32, 100, 64, 52.

  La prima cosa che dobbiamo sapere è se 50 è il root del nostro albero.

  Possiamo ora iniziare a inserire node da node.

  • 76 è maggiore di 50, quindi inserire 76 sul lato destro.
  • 21 è minore di 50, quindi inserire 21 sul lato sinistro.
  • 4 è minore di 50. Node con valore 50 ha un left child 21. Dato che 4 è più piccolo di 21, inseriscilo a sinistra di questo node.
  • 32 è più piccolo di 50. Node con valore 50 ha un left child 21. Poiché 32 è maggiore di 21, inseriamo 32 sul lato destro di questo node.
  • 100 è maggiore di 50. Node con valore 50 ha un right child 76. Poiché 100 è più grande di 76, inseriamo 100 sul lato destro di questo node.
  • 64 è più grande di 50. Node con valore 50 ha un right child 76. Poiché 64 è più piccolo di 76, inseriamo 64 sul lato sinistro di questo node.
  • 52 è maggiore di 50. Node con valore 50 ha un right child 76. Poiché 52 è più piccolo di 76, node con valore 76 ha un left child 64. 52 è più piccolo di 64, quindi inserisci 54 sul lato sinistro di questo node.

  Nota uno schema qui?

  1. Il nuovo node valore è maggiore o minore dell’attuale node?
  2. Se il valore del nuovo node è maggiore dell’attuale node, vai a destra subtree. Se l’attuale node non ha un right child, inseritelo lì, altrimenti tornate al passo #1.
  3. Se il valore del nuovo node è più piccolo dell’attuale node, andate a sinistra subtree. Se l’attuale node non ha un left child, inseriscilo lì, altrimenti torna al passo #1.
  4. Non abbiamo gestito casi speciali qui. Quando il valore di un nuovo node è uguale al valore corrente del node, usa la regola numero 3. Considera di inserire valori uguali al lato sinistro del subtree.

  Ora codifichiamo.

  Sembra molto semplice.

  La parte potente di questo algoritmo è la parte di ricorsione, che è sulla linea 9 e sulla linea 13. Entrambe le linee di codice chiamano il metodo insert_node, e lo usano rispettivamente per i suoi left e rightchildren. Le linee 11 e 15 sono quelle che fanno l’inserimento per ogni child.

  Cerchiamo il valore del nodo… Oppure no…

  L’algoritmo che costruiremo ora riguarda il fare ricerche. Per un dato valore (numero intero), diremo se il nostro Binary Search Tree ha o non ha quel valore.

  Un elemento importante da notare è come abbiamo definito l’algoritmo di inserimento dell’albero. Prima abbiamo il nostro rootnode. Tutti i subtree di sinistra nodes avranno valori più piccoli del rootnode. E tutti i subtreenodes di destra avranno valori maggiori del rootnode.

  Guardiamo un esempio.

  Immaginiamo di avere questo tree.

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

  Facciamo un esempio.

  1. Iniziamo con il rootnode come nostro node attuale. Il valore dato è più piccolo del valore attuale node? Se sì, allora lo cercheremo sulla sinistra subtree.
  2. Il valore dato è maggiore del valore attuale node? Se sì, allora lo cercheremo sulla destra subtree.
  3. Se le regole #1 e #2 sono entrambe false, possiamo confrontare il valore corrente node e il valore dato se sono uguali. Se il confronto restituisce true, allora possiamo dire: “Sì! Il nostro tree ha il valore dato,” altrimenti, diciamo, “Nooo, non l’ha fatto.”

  Ora codifichiamo.

  Facciamo il codice:

  • Le linee 8 e 9 rientrano nella regola #1.
  • Le linee 10 e 11 rientrano nella regola #2.
  • La linea 13 rientra nella regola #3.

  Come lo testiamo?

  Creiamo il nostro Binary Search Tree inizializzando il rootnode con il valore 15.

  bst = BinarySearchTree(15)

  E ora inseriremo molti nuovi nodes.

  Per ogni node inserito, testeremo se il nostro metodo find_node funziona davvero.

  Sì, funziona per questi valori dati! Testiamo un valore che non esiste nel nostro Binary Search Tree.

  print(bst.find_node(0)) # False

  Oh sì.

  La nostra ricerca è fatta.

  Cancellazione: rimuovere e organizzare

  La cancellazione è un algoritmo più complesso perché dobbiamo gestire diversi casi. Per un dato valore, dobbiamo rimuovere il node con questo valore. Immaginate i seguenti scenari per questo node: non ha nessun children, ha un solo child, o ha due children.

  • Scenario #1: Un node senza childrenleafnode).

  # |50| |50|# / \ / \# |30| |70| (DELETE 20) ---> |30| |70|# / \ \# |20| |40| |40|

  Se il node che vogliamo cancellare non ha figli, lo cancelliamo semplicemente. L’algoritmo non ha bisogno di riorganizzare il tree.

  • Scenario #2: Un node con un solo figlio (left o right figlio).

  # |50| |50|# / \ / \# |30| |70| (DELETE 30) ---> |20| |70|# / # |20|

  In questo caso, il nostro algoritmo deve far sì che il genitore del node punti al nodo child. Se il node è il left child, facciamo puntare il genitore del left child al child. Se il node è il right child del suo genitore, facciamo puntare il genitore del right child al child.

  • Scenario #3: Un node con due bambini.

  # |50| |50|# / \ / \# |30| |70| (DELETE 30) ---> |40| |70|# / \ /# |20| |40| |20|

  Quando il node ha 2 figli, dobbiamo trovare il node con il valore minimo, partendo dal node‘sright child. Metteremo questo node con valore minimo al posto del node che vogliamo rimuovere.

  E’ il momento di codificare.

  1. Prima: Notate i parametri value e parent. Vogliamo trovare il node che ha questo value , e il genitore del node è importante per la rimozione del node. Il nostro algoritmo restituirà un valore booleano. Restituisce True se trova il node e lo rimuove. Altrimenti restituisce False.
  2. Dalla linea 2 alla linea 9: Iniziamo a cercare il node che ha il value che stiamo cercando. Se il value è più piccolo del current nodevalue , andiamo al left subtree, ricorsivamente (se, e solo se, il current node ha un left child). Se il value è maggiore, vai al right subtree, ricorsivamente.
  3. Linea 10: Cominciamo a pensare all’algoritmo remove.
  4. Dalla linea 11 alla linea 13: Copriamo il node senza children , ed è il left child dal suo parent. Rimuoviamo il node impostando il parent del left child a None.
  5. Linee 14 e 15: Copriamo il node senza children , ed è il right child dal suo parent. Rimuoviamo il node impostando il parent del right child a None.
  6. Metodo Clear node: Mostrerò il codice clear_node qui sotto. Imposta i nodi left child , right child, e il suo value a None.
  7. Dalla linea 16 alla linea 18: Copriamo il node con un solo childleft child), ed è il left child dal suo parent. Impostiamo il parent del left child al node del left child (l’unico figlio che ha).
  8. Dalla linea 19 alla linea 21: Copriamo il node con un solo childleft child), ed è il right child del suo parent. Impostiamo il parent del right child al node del left child (l’unico figlio che ha).
  9. Dalla linea 22 alla linea 24: Copriamo il node con un solo childright child), ed è il left child dal suo parent. Impostiamo il parent del left child al node del right child (l’unico figlio che ha).
  10. Dalla linea 25 alla linea 27: Copriamo il node con un solo childright child) , ed è il right child del suo parent. Impostiamo il parent del right child al node del right child (l’unico figlio che ha).
  11. Dalla linea 28 alla linea 30: Copriamo il node con entrambi i left e rightfigli. Prendiamo il node con il più piccolo value (il codice è mostrato sotto) e lo impostiamo sul value del current node . Terminate rimuovendo il più piccolo node.
  12. Linea 32: Se troviamo il node che stiamo cercando, deve restituire True. Dalla linea 11 alla linea 31, gestiamo questo caso. Quindi basta restituire True e questo è tutto.
  • Per usare il metodo clear_node: impostare il valore None su tutti e tre gli attributi – (valueleft_child, e right_child)

  def clear_node(self): self.value = None self.left_child = None self.right_child = None

  • Per usare il metodo find_minimum_value: andare molto in basso a sinistra. Se non troviamo più nodi, abbiamo trovato il più piccolo.

  def find_minimum_value(self): if self.left_child: return self.left_child.find_minimum_value() else: return self.value

  Ora testiamolo.

  Useremo questo tree per testare il nostro remove_node algoritmo.

  # |15|# / \# |10| |20|# / \ / \# |8| |12| |17| |25|# \# |19|

  Togliamo il node con il value 8. E’ un node senza figli.

  print(bst.remove_node(8, None)) # Truebst.pre_order_traversal()# |15|# / \# |10| |20|# \ / \# |12| |17| |25|# \# |19|

  Ora rimuoviamo il node con il value 17. E’ un node con un solo figlio.

  print(bst.remove_node(17, None)) # Truebst.pre_order_traversal()# |15|# / \# |10| |20|# \ / \# |12| |19| |25|

  Infine, rimuoveremo un node con due figli. Questo è il root del nostro tree.

  print(bst.remove_node(15, None)) # Truebst.pre_order_traversal()# |19|# / \# |10| |20|# \ \# |12| |25|

  I test sono ora fatti. 🙂

  E’ tutto per ora!

  Abbiamo imparato molto qui.

  Congratulazioni per aver finito questo denso contenuto. È davvero difficile capire un concetto che non conosciamo. Ma tu ce l’hai fatta 🙂

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

  Divertiti, continua a imparare e a codificare.

  Il mio Twitter & Github. ☺

  Risorse aggiuntive

  • Introduzione alla struttura di dati ad albero da mycodeschool
  • Albero da Wikipedia
  • Come non rimanere bloccati dagli alberi dal talentuoso Vaidehi Joshi
  • Introduzione agli alberi, lezione del Professor Jonathan Cohen
  • Introduzione agli alberi, Lecture by Professor David Schmidt
  • Intro to Trees, Lecture by Professor Victor Adamchik
  • Trees with Gayle Laakmann McDowell
  • Binary Tree Implementation and Tests by TK
  • Coursera Course: Data Structures dell’Università della California, San Diego
  • Corso Coursera: Data Structures and Performance by University of California, San Diego
  • Concetti e implementazione dell’albero di ricerca binaria da Paul Programming
  • Implementazione dell’albero di ricerca binaria e test da TK
  • Tree Traversal da Wikipedia
  • Albero di Ricerca Binario Rimuovi Nodo Algoritmo da GeeksforGeeks
  • Albero di Ricerca Binario Rimuovi Nodo Algoritmo da Algolist
  • Imparare Python Da Zero a Eroe