Gli Alberi Binari in Python

Gli alberi binari in Python sono strumenti fondamentali per organizzare e gestire dati in una struttura gerarchica a due rami. Con Python, la loro implementazione permette una manipolazione agevole dei dati, fornendo una base solida per operazioni come l’inserimento, la ricerca e la rimozione.

[wpda_org_chart tree_id=42 theme_id=50]

Gli alberi Binari

Un albero binario è una struttura dati gerarchica composta da nodi collegati in modo tale che ciascun nodo può avere al massimo due nodi figli, denominati “figlio sinistro” e “figlio destro”. Ogni nodo, eccetto la radice, ha esattamente un nodo padre. La radice è il nodo principale dell’albero, mentre i nodi che non hanno figli sono chiamati foglie.

• Nodo: Ogni elemento all’interno dell’albero è chiamato nodo. Ogni nodo può avere zero, uno o due nodi figli, a seconda della sua posizione nell’albero.
• Radice: Il nodo superiore dell’albero è la radice. Ogni albero binario ha una sola radice.
• Foglia: I nodi senza nodi figli sono chiamati foglie. Sono i nodi terminali dell’albero.
• Figlio Sinistro e Destro: Ogni nodo può avere al massimo due figli, uno a sinistra e uno a destra. Il figlio sinistro è il nodo figlio posizionato sulla parte sinistra, mentre il figlio destro è quello posizionato sulla parte destra.

Ecco alcune caratteristiche importanti che caratterizzano gli alberi binari

• Ordinamento: In alcuni alberi binari, come gli alberi binari di ricerca (BST), è mantenuta una proprietà di ordinamento, dove i nodi a sinistra di un dato nodo contengono valori inferiori, mentre quelli a destra contengono valori superiori.
• Struttura Ricorsiva: La struttura di un albero binario è ricorsiva, poiché ogni sottoalbero di un nodo è anch’esso un albero binario.

Gli alberi binari sono utilizzati ampiamente in informatica per risolvere una varietà di problemi. Alcuni utilizzi comuni includono la rappresentazione di espressioni matematiche, la creazione di alberi di ricerca binaria per la ricerca efficiente dei dati e la strutturazione dei dati nei compilatori.

In Python, gli alberi binari possono essere implementati attraverso classi e oggetti, sfruttando la flessibilità e la chiarezza del linguaggio per gestire le relazioni tra i nodi in modo efficiente e intuitivo.

Rispetto ai Grafi, gli alberi binari sono un tipo specifico di grafo aciclico (senza cicli) in cui ogni nodo ha al massimo due nodi figli. I grafi possono avere un numero arbitrario di connessioni tra nodi. Gli alberi binari sono spesso utilizzati per rappresentare gerarchie ordinate, mentre i grafi sono più flessibili e possono rappresentare relazioni più complesse.

In sintesi, gli alberi binari forniscono una struttura dati efficiente per rappresentare relazioni gerarchiche e sono particolarmente utili quando è necessario eseguire operazioni di ricerca o organizzare dati in un modo che rifletta le relazioni logiche tra di essi.

Tipologie di Alberi Binari

Esistono diverse tipologie di alberi binari, ognuna delle quali presenta caratteristiche specifiche adatte a differenti contesti e necessità di implementazione. Di seguito, ti presento alcune delle principali tipologie di alberi binari:

• Albero Binario Standard: Ogni nodo ha al massimo due figli: un figlio sinistro e un figlio destro.
• Albero Binario di Ricerca (BST – Binary Search Tree): Struttura di albero binario in cui ciascun nodo ha al massimo due figli, e il valore del nodo a sinistra è minore o uguale al valore del nodo padre, mentre il valore del nodo a destra è maggiore.
• Albero Binario Completo: Un albero binario in cui tutti i livelli sono completamente riempiti, eccetto eventualmente l’ultimo livello che è riempito da sinistra a destra.
• Albero Binario Perfetto: Un albero binario completo in cui tutti i livelli sono completamente riempiti, avendo quindi tutte le foglie allo stesso livello.
• Albero Binario Bilanciato: Un albero binario in cui la differenza tra le altezze dei sottoalberi sinistro e destro di ogni nodo è al massimo uno. Gli alberi AVL sono un esempio di alberi binari bilanciati.
• Albero Binario di Espressione: Un albero binario utilizzato per rappresentare espressioni matematiche, in cui gli operatori sono nei nodi interni e gli operandi sono nelle foglie.
• Albero di Huffman: Un tipo di albero binario utilizzato per la compressione dei dati, in cui i caratteri più frequenti hanno un percorso più breve rispetto a quelli meno frequenti.
• Albero di Segmento: Un albero binario utilizzato in ambito di algoritmi di query su intervalli, che suddivide un array in segmenti e permette di eseguire operazioni efficienti su tali intervalli.
• Albero Trie (o Trie Binario): Un tipo di albero binario in cui ogni nodo rappresenta un bit di un numero binario e ogni cammino dalla radice a una foglia rappresenta un numero binario univoco.
• Albero Rosso-Nero: Un tipo di albero binario di ricerca in cui ogni nodo ha un attributo colore (rosso o nero) e vengono applicate regole specifiche per garantire un bilanciamento approssimativo dell’albero.

Ogni tipo di albero binario ha applicazioni specifiche e vantaggi in termini di tempo di esecuzione delle operazioni di ricerca, inserimento ed eliminazione. La scelta del tipo di albero dipende dalle esigenze specifiche del problema che si sta affrontando.

Implementazione in Python degli Alberi Binari

Per implementare un albero binario in Python, puoi utilizzare classi per rappresentare i nodi e l’albero stesso. Ecco un esempio di implementazione di un albero binario di ricerca (BST) in Python:

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

    def __repr__(self):
        return f"Node with value {self.value}"

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        self.root = self._insert(self.root, value)

    def _insert(self, root, value):
        if root is None:
            return Node(value)

        if value < root.value:
            root.left_child = self._insert(root.left_child, value)
        elif value > root.value:
            root.right_child = self._insert(root.right_child, value)

        return root

    def search(self, value):
        return self._search(self.root, value)

    def _search(self, root, value):
        if root is None or root.value == value:
            return root
        if value < root.value:
            return self._search(root.left_child, value)
        return self._search(root.right_child, value)

    def in_order_traversal(self):
        result = []
        self._in_order_traversal(self.root, result)
        return result

    def _in_order_traversal(self, root, result):
        if root:
            self._in_order_traversal(root.left_child, result)
            result.append(root.value)
            self._in_order_traversal(root.right_child, result)

# Example usage:
tree = BinarySearchTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(1)
tree.insert(4)

print(tree.in_order_traversal())  
print(tree.search(4))  
print(tree.search(6)) 

In questo esempio, abbiamo una classe Node che rappresenta un singolo nodo dell’albero e una classe BinarySearchTree che rappresenta l’albero binario di ricerca. L’albero è implementato con operazioni di inserimento e ricerca. L’attraversamento in ordine viene utilizzato per ottenere una lista ordinata degli elementi nell’albero. Eseguendo il codice si ottiene il seguente risultato:

[1, 3, 4, 5, 7]
Node with value 4
None

Questo è solo un esempio base, e le implementazioni possono variare in base alle esigenze specifiche del tuo progetto.

Visualizzare gli Alberi Binari con Graphviz

Graphviz è un insieme di strumenti open source per la visualizzazione di grafici. Consente di descrivere la struttura di un grafo attraverso un linguaggio di descrizione e di generare visualizzazioni grafiche del grafo in vari formati, come immagini PNG, PDF o SVG. Graphviz è ampiamente utilizzato per visualizzare la struttura di alberi, grafi, reti, schemi concettuali e altro ancora.

Il componente chiave di Graphviz è dot, un programma da riga di comando che legge la descrizione di un grafo e produce un file contenente la sua rappresentazione visiva.

1. Installare Graphviz:
   Assicurati che Graphviz sia installato sul tuo sistema. Puoi scaricarlo da Graphviz Download.
2. Aggiungere Graphviz al PATH:
   Dopo l’installazione, assicurati che il percorso (PATH) all’eseguibile dot di Graphviz sia aggiunto alle variabili di ambiente del tuo sistema.
3. Verifica l’Installazione di Graphviz:
   Verifica che Graphviz sia correttamente installato eseguendo il comando dot da una finestra del terminale o prompt dei comandi. Dovresti vedere un elenco di opzioni di utilizzo.

Modulo Python per Graphviz:

Per interagire con Graphviz attraverso Python, puoi utilizzare il modulo graphviz. Questo modulo fornisce un’interfaccia Python per generare file di descrizione del grafo compatibili con Graphviz e per eseguire il rendering di questi file in vari formati di immagine.

Per installare il modulo graphviz, puoi utilizzare il seguente comando:

pip install graphviz

Dopo l’installazione, puoi utilizzare il modulo Python nel tuo codice per generare descrizioni di grafi e visualizzazioni. L’uso del modulo Graphviz in Python è ciò che abbiamo fatto nel codice di esempio precedente per visualizzare l’albero binario.

from graphviz import Digraph

# Creazione di un oggetto Digraph
dot = Digraph(comment='Nome del Grafo')

# Aggiunta dei nodi e degli archi
dot.node('A', 'Node A')
dot.node('B', 'Node B')
dot.edge('A', 'B', label='Edge AB')

# Salvataggio del grafo in un file e rendering in un formato specifico (es. PNG)
dot.render('nome_del_grafo', format='png', cleanup=True)

Questo codice crea un grafo diretto (Digraph), aggiunge alcuni nodi e un arco, e quindi rende il grafo in formato PNG. Il file risultante può essere visualizzato come immagine o incorporato in un Jupyter Notebook.

Modifichiamo l’esempio precedente

Effettuiamo delle modifiche al programma di esempio usato in precedenza integrando Graphviz.

from graphviz import Digraph

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

    def __repr__(self):
        return f"Node with value {self.value}"

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        self.root = self._insert(self.root, value)

    def _insert(self, root, value):
        if root is None:
            return Node(value)

        if value < root.value:
            root.left_child = self._insert(root.left_child, value)
        elif value > root.value:
            root.right_child = self._insert(root.right_child, value)

        return root

    def search(self, value):
        return self._search(self.root, value)

    def _search(self, root, value):
        if root is None or root.value == value:
            return root
        if value < root.value:
            return self._search(root.left_child, value)
        return self._search(root.right_child, value)

    def in_order_traversal(self):
        result = []
        self._in_order_traversal(self.root, result)
        return result

    def _in_order_traversal(self, root, result):
        if root:
            self._in_order_traversal(root.left_child, result)
            result.append(root.value)
            self._in_order_traversal(root.right_child, result)

    def visualize(self, filename='tree'):
        dot = Digraph(comment='Binary Search Tree')
        self._add_nodes(dot, self.root)
        dot.render(filename, format='png', cleanup=True)

    def _add_nodes(self, dot, root):
        if root:
            dot.node(str(root.value))
            if root.left_child:
                dot.edge(str(root.value), str(root.left_child.value), label='L')
                self._add_nodes(dot, root.left_child)
            if root.right_child:
                dot.edge(str(root.value), str(root.right_child.value), label='R')
                self._add_nodes(dot, root.right_child)

# Example usage:
tree = BinarySearchTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(1)
tree.insert(4)

tree.visualize('bst')

Eseguendo si otterrà nella working directory un file PNG con l’immagine del nostro grafo. Se vogliamo visualizzarlo su IPython, o Jupypter Lab o Notebook, possiamo usare il codice seguente:

from IPython.display import Image, display

display(Image(filename='bst.png'))  

Si otterrà l’albero binario mostrato in figura sotto.

Algoritmi Principali – Attraversamenti dell’Albero (Traversal)

Gli attraversamenti degli alberi binari sono operazioni fondamentali che consentono di visitare tutti i nodi dell’albero seguendo un determinato ordine. Ci sono tre tipi principali di attraversamenti: In-Order, Pre-Order e Post-Order. Ognuno di essi definisce un modo diverso di visitare i nodi, influenzando l’ordine in cui vengono esplorati.

1. In-Order Traversal:

• In un attraversamento in ordine, si visita il nodo sinistro, quindi il nodo corrente e infine il nodo destro.
• L’ordine di visita è spesso usato con alberi binari di ricerca (BST) poiché garantisce che i nodi vengano visitati in ordine crescente (o decrescente) di valore.

   def in_order_traversal(root):
       if root:
           in_order_traversal(root.left_child)
           print(root.value)
           in_order_traversal(root.right_child)

2. Pre-Order Traversal:

• In un attraversamento pre-ordine, si visita prima il nodo corrente, poi il nodo sinistro e infine il nodo destro.
• Utile per copiare la struttura dell’albero, calcolare espressioni prefisse o effettuare operazioni di pre-elaborazione.

   def pre_order_traversal(root):
       if root:
           print(root.value)
           pre_order_traversal(root.left_child)
           pre_order_traversal(root.right_child)

3. Post-Order Traversal:

• In un attraversamento post-ordine, si visita prima il nodo sinistro, poi il nodo destro e infine il nodo corrente.
• Può essere utilizzato per eseguire operazioni di post-elaborazione, ad esempio deallocazione di memoria.

   def post_order_traversal(root):
       if root:
           post_order_traversal(root.left_child)
           post_order_traversal(root.right_child)
           print(root.value)

Esempio di Utilizzo:

# Creazione di un albero binario di esempio
tree = BinarySearchTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(1)
tree.insert(4)

# Attraversamento In-Order
print("In-Order Traversal:")
tree.in_order_traversal()  # Output: [1, 3, 4, 5, 7]

# Attraversamento Pre-Order
print("\nPre-Order Traversal:")
tree.pre_order_traversal()  # Output: [5, 3, 1, 4, 7]

# Attraversamento Post-Order
print("\nPost-Order Traversal:")
tree.post_order_traversal()  # Output: [1, 4, 3, 7, 5]

In questo esempio, si mostra come eseguire ognuno degli attraversamenti su un albero binario di ricerca. Modifica il codice in base alle tue esigenze specifiche.

Algoritmi Principali – Ricerca in Alberi Binari di Ricerca (BST)

La ricerca in un Albero Binario di Ricerca (BST) è un’operazione fondamentale che sfrutta la struttura ordinata dell’albero per trovare un elemento specifico in modo efficiente. Gli alberi binari di ricerca sono progettati in modo tale che per ogni nodo, tutti i nodi nel sottoalbero sinistro hanno valori inferiori, mentre tutti quelli nel sottoalbero destro hanno valori superiori. Questa caratteristica semplifica notevolmente l’operazione di ricerca.

Descrizione dell’Algoritmo di Ricerca in un BST:

Inizia dalla Radice: L’operazione di ricerca inizia dalla radice dell’albero.

Confronta con il Valore del Nodo Corrente: Confronta il valore da cercare con il valore del nodo corrente.

Scelta del Percorso:

• Se il valore cercato è uguale al valore del nodo corrente, l’elemento è stato trovato, e l’operazione termina con successo.
• Se il valore cercato è inferiore al valore del nodo corrente, prosegui nella ricerca nel sottoalbero sinistro.
• Se il valore cercato è superiore al valore del nodo corrente, prosegui nella ricerca nel sottoalbero destro.

Ripeti il Processo: Ripeti i passaggi 2 e 3 ricorsivamente nel sottoalbero appropriato fino a quando l’elemento è trovato o si raggiunge una foglia (nodo senza figli).

Elemento Non Trovato: Se l’elemento non è stato trovato al termine della ricerca, l’algoritmo restituirà un valore indicativo (ad esempio, None in Python) per indicare che l’elemento non è presente nell’albero.

Implementazione in Python:

def search_in_bst(root, value):
    # Base case: tree is empty or value is in the root
    if root is None or root.value == value:
        return root
    # If the value is less, search in the left subtree
    if value < root.value:
        return search_in_bst(root.left_child, value)
    # If the value is greater, search in the right subtree
    return search_in_bst(root.right_child, value)

Esempio di Utilizzo:

# Creating an example binary search tree
tree = BinarySearchTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(1)
tree.insert(4)

# Searching for a value in the tree
searched_value = 4
search_result = search_in_bst(tree.root, searched_value)

if search_result:
    print(f"Element {searched_value} found in the tree.")
else:
    print(f"Element {searched_value} not found in the tree.")

In questo esempio, l’algoritmo di ricerca viene utilizzato per cercare il valore 4 nell’albero binario di ricerca. Il risultato viene poi stampato a scopo illustrativo.

Algoritmi Principali – Inserimento ed Eliminazione in Alberi Binari

L’inserimento e l’eliminazione di nodi in un Albero Binario sono operazioni essenziali che mantengono la struttura e la proprietà ordinata dell’albero. L’inserimento di un nuovo nodo è necessario quando si desidera aggiungere un elemento all’albero, mentre l’eliminazione è utile per rimuovere un nodo specifico dall’albero senza compromettere la struttura binaria e l’ordinamento.

Inserimento in un Albero Binario:

L’algoritmo di inserimento in un albero binario prevede la ricerca del posto corretto per il nuovo nodo all’interno dell’albero in base al suo valore. Dopo la ricerca, il nodo viene inserito come figlio del nodo trovato.

def insert_into_tree(root, value):
    # Base case: tree is empty or leaf node
    if root is None:
        return Node(value)
    
    # Insert into the left subtree if the value is smaller
    if value < root.value:
        root.left_child = insert_into_tree(root.left_child, value)
    # Insert into the right subtree if the value is greater
    elif value > root.value:
        root.right_child = insert_into_tree(root.right_child, value)

    return root

Eliminazione da un Albero Binario:

L’operazione di eliminazione in un albero binario è più complessa rispetto all’inserimento e prevede diversi casi da gestire. In generale, si cerca il nodo da eliminare e, a seconda del numero di figli del nodo, si effettua l’eliminazione in modo appropriato.

def delete_from_tree(root, value):
    # Base case: tree is empty
    if root is None:
        return root
    
    # Search for the node to be deleted in the left subtree
    if value < root.value:
        root.left_child = delete_from_tree(root.left_child, value)
    # Search for the node to be deleted in the right subtree
    elif value > root.value:
        root.right_child = delete_from_tree(root.right_child, value)
    # Node to be deleted found
    else:
        # Case 1: Node with no child or only one child
        if root.left_child is None:
            return root.right_child
        elif root.right_child is None:
            return root.left_child

        # Case 2: Node with two children
        # Find the smallest (or largest) successor (or predecessor) in the right (or left) subtree
        root.value = find_min_value_node(root.right_child).value
        # Delete the successor (predecessor) in the right (left) subtree
        root.right_child = delete_from_tree(root.right_child, root.value)

    return root

def find_min_value_node(node):
    current = node
    while current.left_child is not None:
        current = current.left_child
    return current

Esempio di Utilizzo:

# Creating an example binary search tree
tree = BinarySearchTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(1)
tree.insert(4)

# Inserting a new node
new_value = 6
tree.root = insert_into_tree(tree.root, new_value)

# Deleting an existing node
node_to_delete = 3
tree.root = delete_from_tree(tree.root, node_to_delete)

In questo esempio, vengono eseguite operazioni di inserimento ed eliminazione in un albero binario di ricerca. Modifica il codice in base alle tue esigenze specifiche.

Bilanciamento degli Alberi Binari e Introduzione agli Alberi AVL

Gli Alberi Binari di Ricerca (BST) possono degenerare in strutture inefficienti, specialmente in caso di inserimenti o eliminazioni frequenti. Per mantenere un tempo di ricerca efficiente, sono stati sviluppati alberi bilanciati, tra cui gli Alberi AVL.

Concetto di Bilanciamento

In un Albero AVL, la differenza di altezza tra il sottoalbero sinistro e destro di ogni nodo, chiamata fattore di bilanciamento, deve essere compresa tra -1, 0 e 1. Se il fattore di bilanciamento di un nodo è maggiore di 1 o inferiore a -1, l’albero è sbilanciato e richiede operazioni di rotazione per ripristinare il bilanciamento.

Implementazione di un Albero AVL in Python:

Ecco una guida passo-passo su come implementare un Albero AVL in Python:

1. Definire la Struttura del Nodo AVL:

• Ogni nodo deve avere un valore, un riferimento al sottoalbero sinistro e un riferimento al sottoalbero destro. Aggiungi anche l’altezza del nodo.

   class AVLNode:
       def __init__(self, value):
           self.value = value
           self.left_child = None
           self.right_child = None
           self.height = 1

2. Definire l’Albero AVL:

• L’Albero AVL avrà un riferimento alla radice.

   class AVLTree:
       def __init__(self):
           self.root = None

3. Implementare le Rotazioni:

• Le rotazioni sono le operazioni chiave per mantenere il bilanciamento.
• Rotazione a sinistra (left_rotate) e rotazione a destra (right_rotate) sono necessarie.

   def left_rotate(self, z):
       y = z.right_child
       T2 = y.left_child

       y.left_child = z
       z.right_child = T2

       z.height = 1 + max(self._get_height(z.left_child), self._get_height(z.right_child))
       y.height = 1 + max(self._get_height(y.left_child), self._get_height(y.right_child))

       return y

   def right_rotate(self, y):
       x = y.left_child
       T2 = x.right_child

       x.right_child = y
       y.left_child = T2

       y.height = 1 + max(self._get_height(y.left_child), self._get_height(y.right_child))
       x.height = 1 + max(self._get_height(x.left_child), self._get_height(x.right_child))

       return x

4. Implementare l’Inserimento:

• Inserire un nodo nell’albero seguendo il normale processo di inserimento di un BST.
• Dopo l’inserimento, assicurarsi che l’albero sia bilanciato.

   def insert(self, root, value):
       # Esegui l'inserimento come in un BST normale
       if not root:
           return AVLNode(value)
       elif value < root.value:
           root.left_child = self.insert(root.left_child, value)
       else:
           root.right_child = self.insert(root.right_child, value)

       # Aggiorna l'altezza del nodo corrente
       root.height = 1 + max(self._get_height(root.left_child), self._get_height(root.right_child))

       # Bilancia l'albero
       return self._balance(root, value)

5. Bilanciare l’Albero Dopo l’Inserimento:

• Utilizzare i fattori di bilanciamento per decidere quale tipo di rotazione eseguire.

   def _balance(self, root, value):
       balance = self._get_balance(root)

       # Caso 1: Sbilanciamento a sinistra del sottoalbero sinistro
       if balance > 1 and value < root.left_child.value:
           return self.right_rotate(root)

       # Caso 2: Sbilanciamento a destra del sottoalbero destro
       if balance < -1 and value > root.right_child.value:
           return self.left_rotate(root)

       # Caso 3: Sbilanciamento a sinistra del sottoalbero destro
       if balance > 1 and value > root.left_child.value:
           root.left_child = self.left_rotate(root.left_child)
           return self.right_rotate(root)

       # Caso 4: Sbilanciamento a destra del sottoalbero sinistro
       if balance < -1 and value < root.right_child.value:
           root.right_child = self.right_rotate(root.right_child)
           return self.left_rotate(root)

       return root

6. Altro:

• Implementare l’eliminazione e altre funzionalità secondo necessità.

6. Esempio di Utilizzo:

• Creare un oggetto AVLTree e utilizzare i metodi di inserimento e altre operazioni.

# Esempio di utilizzo
avl_tree = AVLTree()
avl_tree.root = avl_tree.insert(avl_tree.root, 10)
avl_tree.root = avl_tree.insert(avl_tree.root, 20)
avl_tree.root = avl_tree.insert(avl_tree.root, 30)

Riscriviamo tutto il codice, inserendo anche la visualizzazione grafica, mediante graphviz.

from graphviz import Digraph

class AVLNode:
    def __init__(self, value):
        self.value = value
        self.left_child = None
        self.right_child = None
        self.height = 1

class AVLTree:
    def __init__(self):
        self.root = None

    def visualize(self, filename='avl_tree'):
        dot = Digraph(comment='AVL Tree')
        self._add_nodes(dot, self.root)
        dot.render(filename, format='png', cleanup=True)
        dot.view()

    def _add_nodes(self, dot, root):
        if root:
            dot.node(str(root.value) + f' ({root.height})')
            if root.left_child:
                dot.edge(str(root.value), str(root.left_child.value))
                self._add_nodes(dot, root.left_child)
            if root.right_child:
                dot.edge(str(root.value), str(root.right_child.value))
                self._add_nodes(dot, root.right_child)

    def _get_height(self, root):
        if root is None:
            return 0
        return root.height

    def _get_balance(self, root):
        if root is None:
            return 0
        return self._get_height(root.left_child) - self._get_height(root.right_child)

    def left_rotate(self, z):
        y = z.right_child
        T2 = y.left_child

        y.left_child = z
        z.right_child = T2

        z.height = 1 + max(self._get_height(z.left_child), self._get_height(z.right_child))
        y.height = 1 + max(self._get_height(y.left_child), self._get_height(y.right_child))

        return y

    def right_rotate(self, y):
        x = y.left_child
        T2 = x.right_child

        x.right_child = y
        y.left_child = T2

        y.height = 1 + max(self._get_height(y.left_child), self._get_height(y.right_child))
        x.height = 1 + max(self._get_height(x.left_child), self._get_height(x.right_child))

        return x

    def insert(self, root, value):
        if not root:
            return AVLNode(value)
        elif value < root.value:
            root.left_child = self.insert(root.left_child, value)
        else:
            root.right_child = self.insert(root.right_child, value)

        root.height = 1 + max(self._get_height(root.left_child), self._get_height(root.right_child))

        return self._balance(root)

    def _balance(self, root):
        balance = self._get_balance(root)

        if balance > 1:
            if root.left_child and value < root.left_child.value:
                return self.right_rotate(root)
            if root.left_child and value > root.left_child.value:
                root.left_child = self.left_rotate(root.left_child)
                return self.right_rotate(root)

        if balance < -1:
            if root.right_child and value > root.right_child.value:
                return self.left_rotate(root)
            if root.right_child and value < root.right_child.value:
                root.right_child = self.right_rotate(root.right_child)
                return self.left_rotate(root)

        return root

# Example usage:
avl_tree = AVLTree()
avl_tree.root = avl_tree.insert(avl_tree.root, 10)
avl_tree.root = avl_tree.insert(avl_tree.root, 20)
avl_tree.root = avl_tree.insert(avl_tree.root, 30)
avl_tree.visualize('avl_tree_operations')

Eseguendo si ottiene la seguente immagine:

Ricorda che questa è solo una guida di base. La gestione completa degli inserimenti, delle eliminazioni e degli altri aspetti può richiedere una maggior complessità nel codice. Inoltre, spesso le librerie esistenti in Python, come avl_tree nel modulo bintrees, semplificano l’implementazione di alberi AVL.