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).
[wpda_org_chart tree_id=42 theme_id=50]
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:
- Inserimento: Aggiungere un nuovo elemento all’albero rispettando la proprietà di ordinamento.
- Ricerca: Trovare un elemento nell’albero.
- Cancellazione: Rimuovere un elemento dall’albero.
- Attraversamenti: Visitare tutti i nodi dell’albero in un certo ordine (inorder, preorder, postorder).
- 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 classeBinarySearchTree. Inizializza la radice dell’albero aNone.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
\
5In 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:
- Prestazioni più uniformi: Gli alberi bilanciati garantiscono che le operazioni di ricerca, inserimento e cancellazione abbiano prestazioni uniformi e non degenerino in casi estremi.
- 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:
- 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.
- 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.
- 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.
- 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 35In 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.