Implementa la struttura dei dati ad albero in Python

Nella struttura dati, un albero è un tipo di struttura dati non lineare costituita da nodi collegati. Un albero ha tipicamente un singolo nodo radice che indica il punto di partenza della struttura dati.

Gli alberi sono uno degli argomenti più impegnativi da apprendere nelle strutture dati e nella programmazione. Dal punto di vista dell’applicazione, gli alberi vengono generalmente utilizzati per l’archiviazione efficiente dei dati e per un rapido attraversamento e indicizzazione durante la ricerca dei dati.

Questo tutorial dimostrerà come implementare la struttura dei dati ad albero in Python. Per questo tutorial, ci concentreremo sull’implementazione di alberi binari.

Gli alberi binari sono i più facili da ricordare e implementare, quindi questo sarà l’obiettivo principale di questo tutorial.

Implementa manualmente una classe Tree in Python

Python non è esattamente noto per essere orientato agli oggetti e non supporta le strutture dati tanto quanto altri linguaggi che si concentrano sulla creazione di oggetti.

Poiché Python supporta la creazione e l’istanza di classi, implementa gli alberi creando una classe Tree e definisci i campi. Un’istanza di dati in un albero è chiamata node. Gli alberi sono composti da nodi, con un singolo nodo radice che può estendersi indefinitamente.

Gli alberi binari sono la struttura più comune degli alberi. La distinzione principale che un albero è un albero binario è che possono esserci solo al massimo due nodi figli per nodo padre.

Ecco una rappresentazione visiva di come potrebbe apparire un albero binario.

Albero

Nella rappresentazione visiva di un albero sopra, A è il nodo radice. Osserva che ogni nodo può avere al massimo due figli o nessun figlio.

Dichiara un albero

Per dichiarare un albero binario in Python, creare una classe Tree con una funzione __init__() che istanzerà questi tre campi di classe: il nodo figlio sinistro, il nodo figlio destro e i dati del nodo corrente. I tre campi menzionati sono la composizione di un semplice albero binario.

class Tree:
  def __init__(self):
    self.val = None
    self.left = None
    self.right = None

La funzione __init__() è la versione di Python di un costruttore di classi in OOP. Questa è la funzione chiamata quando viene creata un’istanza della classe Tree. In questo caso, imposta inizialmente il valore e i nodi figli su None.

Un altro approccio per dichiarare un albero in Python consiste nell’includere facoltativamente il valore di un albero all’interno del costruttore. Per fare questo, aggiungi un secondo parametro alla funzione __init__() che rappresenta il valore dell’albero e inizializzalo su None per renderlo un parametro opzionale.

class Tree:
  def __init__(self, val = None):
    if val != None:
        self.val = val
    else:
        self.val = None
        
    self.left = None
    self.right = None

Questo approccio consente di avere il valore dell’albero istanziato insieme all’albero reale e allo stesso tempo di impostarlo a None se non c’è alcun argomento val.

Crea un’istanza di un albero

Ora che la dichiarazione di un albero binario è coperta, possiamo ora istanziare un’istanza di un albero.

Per fare ciò, chiamiamo semplicemente il costruttore dell’oggetto usando il nome dell’oggetto. In questo caso, sarebbe Tree() poiché la funzione __init__() non contiene argomenti tranne se stessa.

Ad esempio, per istanziare un albero senza argomenti:

tree = Tree()

print(tree)

Produzione:

<__main__.Tree object at 0x10cd98dd8>

L’output rappresenta l’area della memoria allocata per l’oggetto albero che è stato appena istanziato.

Per aggiungere manualmente un valore all’albero, assegnare un valore all’oggetto val all’interno dell’albero appena istanziato.

tree = Tree()
tree.val = 20
print(tree.val)

Produzione:

20

Usare l’approccio alternativo che accetta il campo val come argomento accorcerà ulteriormente questa operazione.

tree = Tree(20)
print(tree.val)

Produzione:

20

Entrambi gli approcci eseguiranno la stessa azione sebbene quest’ultimo sia notevolmente più efficiente.

Ora, per istanziare i figli dell’albero esistente, fai semplicemente la stessa cosa sopra ma ai campi left e right all’interno dell’oggetto tree.

tree = Tree(20)
tree.left = Tree(18)
tree.right = Tree(22)

print(tree.left.val)
print(tree.right.val)

Produzione:

18
22

Se illustriamo questo come la rappresentazione visiva sopra, l’albero inizialmente sarebbe simile a questo:

Valori dell'albero binario di Python

La regola principale di un albero binario è che tutti i nodi all’interno dell’albero sono disposti in un ordine specifico. Questo viene fatto in modo che l’attraversamento di un albero binario sia supportato con una sorta di logica. In questo caso, la logica è che l’albero contiene valori interi ed è disposto in ordine crescente da sinistra a destra.

Ora, come procediamo con l’inserimento di un nuovo elemento nell’albero?

Inserisci un elemento in un albero esistente

Per inserire un elemento in un albero esistente, aggiungi una nuova funzione, insert(), nella classe Tree. La funzione accetta due parametri: il parametro autoreferenziale self e il valore da inserire val.

La funzione insert() inserisce il valore val nell’albero attraversando l’albero per individuare dove il valore deve essere inserito in base alla logica data. Anche in questo caso, la logica per l’esempio in questo articolo è in ordine crescente in base ai valori interi.

Questa funzione è per natura ricorsiva, il che significa che può salire e scendere dall’albero a seconda della logica dichiarata. Le funzioni ricorsive sono funzioni che ripetutamente chiamano se stesse all’interno della funzione fino a quando non raggiunge una condizione di uscita.

def insert(self, val):
  if self.val:
      if val < self.val:
      		if self.left is None:
          		self.left = Tree(val)
        	else:
          		self.left.insert(val)
      elif val > self.val:
        	if self.right is None:
          		self.right = Tree(val)
        	else:
          		self.right.insert(val)
  else:
    self.val = val

La funzione sopra esegue quanto segue:

  • Se il valore del nodo corrente è vuoto, la funzione assegna val al nodo corrente.
  • Se il valore del nodo corrente è maggiore del valore da inserire, verificare se il nodo corrente ha un figlio sinistro
    • Se il figlio sinistro esiste, chiama di nuovo la funzione insert(), con il figlio sinistro come argomento autoreferenziale (chiamata ricorsiva).
    • Se il figlio sinistro non esiste, assegna val al nodo corrente.
  • Se il valore del nodo corrente è minore del valore da inserire, verificare se il nodo corrente ha un figlio sinistro
    • Se il figlio destro esiste, chiama di nuovo la funzione insert(), con il figlio destro come argomento autoreferenziale (chiamata ricorsiva).
    • Se il figlio giusto non esiste, assegna val al nodo corrente.

Notare che gli alberi binari inseriranno sempre valori e non sostituiranno né sposteranno mai alcun valore esistente.

Ora, con l’esempio esistente fornito nell’ultima sezione, proviamo a inserire il numero 19 come nuovo valore nell’albero.

tree = Tree(20)
tree.left = Tree(18)
tree.right = Tree(22)
tree.insert(19)

Idealmente, se la funzione è implementata correttamente, l’albero con il valore appena inserito dovrebbe assomigliare a questo.

Albero Python con valore inserito

Quindi, per stamparlo esplicitamente, sarebbe come di seguito.

tree = Tree(20)
tree.left = Tree(18)
tree.right = Tree(22)
tree.insert(19)

print(tree.left.right)
print(tree.left.right.val)

Produzione:

<__main__.Tree object at 0x109692fd0>
19

Ora, cosa succede se vogliamo stampare l’intero contenuto dell’albero in ordine crescente? Dovrebbe essere implementata anche una funzione di attraversamento.

Attraversa l’intero albero

Per attraversare un albero binario e stampare i contenuti nell’ordine desiderato, dovremmo usare l’attraversamento in ordine. Questo tipo di attraversamento inizia a stampare i valori da sinistra, poi al centro e infine a destra.

Anche le funzioni di attraversamento dell’albero devono essere ricorsive.

Ecco il codice per attraversare l’albero esistente dall’esempio sopra:

def printValues(self):
  if self.left:
    self.left.printValues()
    
  print(self.val)
  
  if self.right:
    self.right.printValues()
    
   

Proviamo questa funzione con l’esempio esistente nell’ultima sezione ma con più elementi inseriti.

tree = Tree(20)
tree.left = Tree(18)
tree.right = Tree(22)
tree.insert(19)
tree.insert(24)
tree.insert(5)
tree.insert(21)

tree.printValues()

Visivamente, l’albero sarebbe simile a questo:

Albero finale

E l’output della funzione printValues() sarebbe:

5
18
19
20
21
22
24

Si prevede che l’output visualizzi il contenuto dell’albero in ordine crescente.

Ecco il codice sorgente compilato finale per l’esempio finale:

class Tree:
  def __init__(self, val = None):
    if val != None:
	    self.val = val
    else:
        self.val = None
    self.left = None
    self.right = None

  def insert(self, val):
    if self.val:
        if val < self.val:
            if self.left is None:
            	self.left = Tree(val)
            else:
            	self.left.insert(val)
        elif val > self.val:
        		if self.right is None:
              self.right = Tree(val)
            else:
              self.right.insert(val)
    else:
        self.val = val

  def printValues(self):
    if self.left:
        self.left.printValues()
    print(self.val)
    if self.right:
        self.right.printValues()

tree = Tree(20)
tree.left = Tree(18)
tree.right = Tree(22)
tree.insert(19)
tree.insert(24)
tree.insert(5)
tree.insert(21)

tree.printValues()

In sintesi, gli alberi binari in Python sono semplici da implementare e istanziare. Dovresti creare manualmente un oggetto albero in Python e creare le funzioni di utilità per l’inserimento e l’attraversamento. Inoltre, dovrebbe esserci una logica specifica per l’implementazione e per le funzioni ricorsive per avere una condizione di uscita. Nel caso di questo tutorial, la logica implementata è costituita da numeri interi disposti in ordine crescente.

Articolo correlato - Python Data Type