Alberi di Ricerca in Python: Dalla Teoria all’Implementazione Pratica

Alberi di ricerca in Python header

Gli alberi di ricerca sono strutture dati che organizzano dati in modo gerarchico. Uno dei tipi più comuni di albero di ricerca è l’albero binario di ricerca (BST), ma esistono anche varianti come gli alberi di ricerca bilanciati (come AVL e rosso-nero) e alberi di ricerca multiway (come gli alberi B).

  • Python
    • Algoritmi
      • Alberi
        e Grafi
      • Strutture dati
        Avanzate
      • Numerici
      • Ordinamento
        e Ricerca
      • Ricorsione
        Backtracking

Albero Binario di Ricerca (BST)

Un albero binario di ricerca è un tipo di albero in cui ogni nodo ha al massimo due figli, il nodo di sinistra contiene valori inferiori a quello del nodo padre, mentre il nodo di destra contiene valori superiori. Questa proprietà rende possibile una ricerca efficiente.

Esistono una serie di operazioni comuni che si applicano agli alberi binari di ricerca:

  1. Inserimento: Aggiungere un nuovo elemento all’albero rispettando la proprietà di ordinamento.
  2. Ricerca: Trovare un elemento nell’albero.
  3. Cancellazione: Rimuovere un elemento dall’albero.
  4. Attraversamenti: Visitare tutti i nodi dell’albero in un certo ordine (inorder, preorder, postorder).
  5. Minimo e Massimo: Trovare il valore minimo e massimo nell’albero.

Ecco un esempio di implementazione di un albero binario di ricerca in Python in cui vengono implementate queste operazioni :

class BinarySearchTree:
    class Node:
        def __init__(self, key):
            self.key = key
            self.left = None
            self.right = None

    def __init__(self):
        self.root = None

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

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

        if key < root.key:
            root.left = self._insert(root.left, key)
        elif key > root.key:
            root.right = self._insert(root.right, key)

        return root

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

    def _search(self, root, key):
        if root is None or root.key == key:
            return root
        elif key < root.key:
            return self._search(root.left, key)
        else:
            return self._search(root.right, key)

    def delete(self, key):
        self.root = self._delete(self.root, key)

    def _delete(self, root, key):
        if root is None:
            return root

        if key < root.key:
            root.left = self._delete(root.left, key)
        elif key > root.key:
            root.right = self._delete(root.right, key)
        else:
            if root.left is None:
                return root.right
            elif root.right is None:
                return root.left

            root.key = self._min_value(root.right)
            root.right = self._delete(root.right, root.key)

        return root

    def _min_value(self, root):
        current = root
        while current.left is not None:
            current = current.left
        return current.key

    def inorder_traversal(self):
        result = []
        self._inorder_traversal(self.root, result)
        return result

    def _inorder_traversal(self, root, result):
        if root:
            self._inorder_traversal(root.left, result)
            result.append(root.key)
            self._inorder_traversal(root.right, result)

    def min_value(self):
        return self._min_value(self.root)

    def max_value(self):
        return self._max_value(self.root)

    def _max_value(self, root):
        current = root
        while current.right is not None:
            current = current.right
        return current.key


# Example usage
bst = BinarySearchTree()
data = [50, 30, 70, 20, 40, 60, 80]

for value in data:
    bst.insert(value)

print("Inorder Traversal:", bst.inorder_traversal())
print("Min Value:", bst.min_value())
print("Max Value:", bst.max_value())

# Delete the node with key 30
bst.delete(30)
print("After deleting key 30:", bst.inorder_traversal())

Eseguendo il codice otterrai il seguente risultato:

Inorder Traversal: [20, 30, 40, 50, 60, 70, 80]
Min Value: 20
Max Value: 80
After deleting key 30: [20, 40, 50, 60, 70, 80]

Ora, vediamo una spiegazione delle parti principali del codice:

  • class BinarySearchTree: Questa è la classe principale che rappresenta un albero binario di ricerca.
  • class Node: Questa è una classe interna che rappresenta un nodo dell’albero.
  • __init__(self): Il metodo di inizializzazione della classe BinarySearchTree. Inizializza la radice dell’albero a None.
  • insert(self, key): Aggiunge un nuovo nodo all’albero con la chiave specificata.
  • _insert(self, root, key): Metodo ricorsivo privato per l’inserimento di un nodo.
  • search(self, key): Cerca un nodo con la chiave specificata nell’albero.
  • _search(self, root, key): Metodo ricorsivo privato per la ricerca di un nodo.
  • delete(self, key): Elimina un nodo con la chiave specificata dall’albero.
  • _delete(self, root, key): Metodo ricorsivo privato per l’eliminazione di un nodo.
  • _min_value(self, root): Trova il valore minimo nell’albero a partire da un certo nodo.
  • inorder_traversal(self): Restituisce una lista con l’attraversamento in-order dell’albero.
  • _inorder_traversal(self, root, result): Metodo ricorsivo privato per l’attraversamento in-order.
  • min_value(self): Restituisce il valore minimo presente nell’albero.
  • max_value(self): Restituisce il valore massimo presente nell’albero.
  • _max_value(self, root): Trova il valore massimo nell’albero a partire da un certo nodo.

Complessità Temporale:

L’inserimento, la ricerca e la cancellazione in un albero binario di ricerca bilanciato hanno una complessità temporale media di O(log n), dove n è il numero di nodi nell’albero. Senza bilanciamento, l’albero può degenerare in una lista collegata, aumentando la complessità a O(n).

Il Bilanciamento di un albero di ricerca

Il concetto di bilanciamento in un albero di ricerca binario è cruciale per garantire prestazioni efficienti nelle operazioni di inserimento, ricerca e cancellazione. Un albero di ricerca binario è considerato bilanciato quando la differenza di altezza tra il sottoalbero sinistro e quello destro di ogni nodo è limitata e non troppo grande. Se un albero è sbilanciato, le operazioni possono degenerare in prestazioni simili a una lista concatenata, aumentando la complessità temporale.

Alberi Sbilanciati:

Gli alberi di ricerca binaria possono diventare sbilanciati in vari modi, ma una delle situazioni più comuni si verifica quando i dati vengono inseriti in ordine crescente o decrescente. In queste circostanze, l’albero rischia di degenerare in una struttura simile a una lista collegata, con un sottoalbero lungo e un altro praticamente inesistente.

Un esempio di albero sbilanciato può essere il seguente:

        1
         \
          2
           \
            3
             \
              4
               \
                5

In questo caso, l’altezza dell’albero è proporzionale al numero di nodi, e quindi le operazioni di ricerca, inserimento e cancellazione possono richiedere un tempo proporzionale al numero di nodi nell’albero, compromettendo l’efficienza dell’algoritmo.

Alberi Bilanciati:

Un albero di ricerca binaria è bilanciato quando, per ogni nodo, le altezze dei sottoalberi sinistro e destro differiscono di al massimo 1. Ci sono diverse strutture di alberi bilanciati, come gli alberi AVL, gli alberi rosso-nero e gli alberi Splay.

Vantaggi degli Alberi Bilanciati:

  1. Prestazioni più uniformi: Gli alberi bilanciati garantiscono che le operazioni di ricerca, inserimento e cancellazione abbiano prestazioni uniformi e non degenerino in casi estremi.
  2. Complessità temporale garantita: In un albero bilanciato, le operazioni hanno una complessità temporale media di O(log n), dove n è il numero di nodi nell’albero.

Alberi AVL

Gli alberi AVL sono un tipo specifico di albero di ricerca binaria bilanciato. In un AVL, la differenza di altezza tra il sottoalbero sinistro e quello destro di ogni nodo è limitata a -1, 0 o 1. Questa regola viene mantenuta dopo ogni operazione di inserimento o cancellazione mediante rotazioni dell’albero.

L’utilizzo degli alberi AVL garantisce un bilanciamento ottimale, ma le rotazioni possono aumentare leggermente il costo delle operazioni rispetto ad altre strutture bilanciate.

In Python, librerie come sortedcontainers o bintrees forniscono implementazioni efficienti di alberi bilanciati. Quando si lavora con alberi di ricerca binaria, è importante considerare il bilanciamento per garantire prestazioni efficienti nelle operazioni chiave.

Ecco un esempio di implementazione di un albero AVL in Python senza l’uso di librerie. Per questo esempio, useremo una classe Node per rappresentare i nodi dell’albero e una classe AVLTree per gestire le operazioni sull’albero AVL.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1  # L'altezza di un nuovo nodo è 1

class AVLTree:
    def insert(self, root, key):
        if not root:
            return Node(key)

        if key < root.key:
            root.left = self.insert(root.left, key)
        elif key > root.key:
            root.right = self.insert(root.right, key)

        root.height = 1 + max(self._get_height(root.left), self._get_height(root.right))

        balance = self._get_balance(root)

        # Rotazioni per mantenere il bilanciamento
        if balance > 1:
            if key < root.left.key:
                return self._rotate_right(root)
            else:
                root.left = self._rotate_left(root.left)
                return self._rotate_right(root)

        if balance < -1:
            if key > root.right.key:
                return self._rotate_left(root)
            else:
                root.right = self._rotate_right(root.right)
                return self._rotate_left(root)

        return root

    def delete(self, root, key):
        if not root:
            return root

        if key < root.key:
            root.left = self.delete(root.left, key)
        elif key > root.key:
            root.right = self.delete(root.right, key)
        else:
            if not root.left:
                return root.right
            elif not root.right:
                return root.left

            min_val_node = self._get_min_value_node(root.right)
            root.key = min_val_node.key
            root.right = self.delete(root.right, min_val_node.key)

        root.height = 1 + max(self._get_height(root.left), self._get_height(root.right))

        balance = self._get_balance(root)

        # Rotazioni per mantenere il bilanciamento
        if balance > 1:
            if self._get_balance(root.left) >= 0:
                return self._rotate_right(root)
            else:
                root.left = self._rotate_left(root.left)
                return self._rotate_right(root)

        if balance < -1:
            if self._get_balance(root.right) <= 0:
                return self._rotate_left(root)
            else:
                root.right = self._rotate_right(root.right)
                return self._rotate_left(root)

        return root

    def search(self, root, key):
        if not root or root.key == key:
            return root

        if key < root.key:
            return self.search(root.left, key)
        else:
            return self.search(root.right, key)

    def _get_height(self, node):
        if not node:
            return 0
        return node.height

    def _get_balance(self, node):
        if not node:
            return 0
        return self._get_height(node.left) - self._get_height(node.right)

    def _rotate_right(self, y):
        x = y.left
        T2 = x.right

        x.right = y
        y.left = T2

        y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))
        x.height = 1 + max(self._get_height(x.left), self._get_height(x.right))

        return x

    def _rotate_left(self, x):
        y = x.right
        T2 = y.left

        y.left = x
        x.right = T2

        x.height = 1 + max(self._get_height(x.left), self._get_height(x.right))
        y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))

        return y

    def _get_min_value_node(self, root):
        current = root
        while current.left:
            current = current.left
        return current

    def inorder_traversal(self, root):
        result = []
        self._inorder_traversal(root, result)
        return result

    def _inorder_traversal(self, root, result):
        if root:
            # Traverse the left subtree
            self._inorder_traversal(root.left, result)
            # Append the current node's key to the result
            result.append(root.key)
            # Traverse the right subtree
            self._inorder_traversal(root.right, result)

# Esempio di utilizzo
avl_tree = AVLTree()
root = None
keys = [9, 5, 10, 0, 6, 11, -1, 1, 2]
for key in keys:
    root = avl_tree.insert(root, key)

print("Albero AVL dopo l'inserimento:", avl_tree.inorder_traversal(root))

# Cerca e cancella il nodo con chiave 10
key_to_search = 10
found_node = avl_tree.search(root, key_to_search)
if found_node:
    print(f"Element with key {key_to_search} found.")
else:
    print(f"Element with key {key_to_search} not found.")

root = avl_tree.delete(root, key_to_search)
print("Albero AVL dopo la cancellazione di 10:", avl_tree.inorder_traversal(root))

In questo esempio, Node rappresenta i nodi dell’albero con l’aggiunta di un campo height per tenere traccia dell’altezza di ogni nodo. La classe AVLTree contiene i metodi per inserire, cancellare e cercare, oltre a funzioni ausiliarie per calcolare l’altezza, il bilanciamento e eseguire le rotazioni necessarie per mantenere l’albero bilanciato. Infine, viene eseguito un esempio di utilizzo inserendo alcune chiavi nell’albero, cercando e cancellando un nodo specifico.

Eseguendo il codice otterrai il seguente risultato:

AVL tree after insertion: [-1, 0, 1, 2, 5, 6, 9, 10, 11]
Element with key 10 found.
AVL tree after deletion of 10: [-1, 0, 1, 2, 5, 6, 9, 11]

Alberi di Ricerca Multiway

Gli alberi di ricerca multiway sono una variante degli alberi di ricerca binaria in cui ogni nodo può avere più di due figli. In un albero multiway, ogni nodo può avere un numero variabile di sottoalberi. Questo modello permette di organizzare i dati in modo più flessibile rispetto agli alberi binari.

Caratteristiche degli Alberi di Ricerca Multiway:

  1. Numero Variabile di Figli: In un albero di ricerca multiway, un nodo può avere zero o più figli. Mentre negli alberi binari ogni nodo ha al massimo due figli, negli alberi multiway non c’è un limite fisso al numero di figli di un nodo.
  2. Struttura Gerarchica: Gli alberi multiway mantengono una struttura gerarchica, dove ogni nodo è collegato a uno o più sottoalberi, ciascuno dei quali è a sua volta un albero.
  3. Flessibilità nell’Organizzazione dei Dati: L’organizzazione dei dati negli alberi multiway può essere più flessibile rispetto agli alberi binari. Questo può essere utile in situazioni in cui i dati possono essere naturalmente organizzati in più di due categorie o livelli.
  4. Operazioni di Ricerca e Inserimento: Le operazioni di ricerca e inserimento negli alberi di ricerca multiway possono variare a seconda dell’implementazione specifica. Tuttavia, il concetto fondamentale è simile a quello degli alberi binari, dove è necessario attraversare l’albero in modo da individuare correttamente il nodo desiderato.

Ecco un esempio semplificato di un albero di ricerca multiway con nodi che possono avere fino a tre figli:

        10
      / | \
     5  20  30
    / \   / | \
   3   7 15 25  35

In questo esempio, il nodo con chiave 10 ha tre figli (5, 20 e 30), e ciascuno di essi può avere un numero variabile di figli. L’albero può essere attraversato utilizzando approcci simili a quelli degli alberi binari.

Gli alberi di ricerca multiway sono utilizzati in situazioni in cui la struttura gerarchica dei dati può essere meglio rappresentata con un numero variabile di figli per ogni nodo. Tuttavia, la scelta tra un albero di ricerca multiway e uno binario dipenderà dalle specifiche esigenze del problema e delle operazioni che si prevede di eseguire sugli alberi.

Di seguito troverai un esempio di implementazione di un albero di ricerca multiway in Python. In questo esempio, utilizzeremo una classe Node per rappresentare i nodi dell’albero e una classe MultiwayTree per gestire le operazioni sull’albero.

class Node:
    def __init__(self, key):
        self.key = key
        self.children = []

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

    def insert(self, key, parent_key=None):
        new_node = Node(key)

        if not parent_key:
            self.root = new_node
        else:
            parent_node = self._search(self.root, parent_key)
            if parent_node:
                parent_node.children.append(new_node)
            else:
                print(f"Parent with key {parent_key} not found. Inserting at the root.")

    def _search(self, root, key):
        if not root:
            return None

        if root.key == key:
            return root

        for child in root.children:
            result = self._search(child, key)
            if result:
                return result

        return None

    def inorder_traversal(self, root=None):
        if not root:
            root = self.root

        result = []
        self._inorder_traversal(root, result)
        return result

    def _inorder_traversal(self, root, result):
        if root:
            for child in root.children:
                self._inorder_traversal(child, result)
            result.append(root.key)

# Esempio di utilizzo
multiway_tree = MultiwayTree()

# Inserisci nodi nell'albero
multiway_tree.insert(10)
multiway_tree.insert(5, parent_key=10)
multiway_tree.insert(20, parent_key=10)
multiway_tree.insert(3, parent_key=5)
multiway_tree.insert(7, parent_key=5)
multiway_tree.insert(15, parent_key=20)
multiway_tree.insert(25, parent_key=20)
multiway_tree.insert(30, parent_key=10)
multiway_tree.insert(35, parent_key=30)

# Stampa l'attraversamento in-order dell'albero multiway
print("Attraversamento Inorder dell'Albero Multiway:", multiway_tree.inorder_traversal())

In questo esempio, la classe Node rappresenta i nodi dell’albero, con il campo children che è una lista contenente i nodi figli. La classe MultiwayTree gestisce le operazioni sull’albero, inclusa l’inserzione di nuovi nodi e l’attraversamento in-order.

Eseguendo il codice otterrai il seguente risultato:

Inorder Traversal of the Multiway Tree: [3, 7, 5, 15, 25, 20, 35, 30, 10]

L’esempio di utilizzo mostra come creare un albero di ricerca multiway inserendo alcuni nodi con relazioni padre-figlio e successivamente stampando l’attraversamento in-order dell’albero. Puoi personalizzare e ampliare questo esempio in base alle tue esigenze.

Conclusioni

Gli alberi di ricerca sono strutture dati fondamentali nella scienza dell’informatica, ampiamente utilizzate per la gestione efficiente di dati ordinati. La corretta gestione della loro struttura è cruciale per mantenere alte prestazioni nelle operazioni di ricerca e inserimento.

Lascia un commento