Albero Binario di Ricerca: funzionamento con esempio
Introduzione
L’albero binario di ricerca (Binary Search Tree, BST) è una struttura dati che facilita operazioni come ricerca, inserimento e cancellazione di elementi in modo efficiente. In un BST, ogni nodo ha al massimo due figli: il figlio sinistro contiene un valore minore rispetto al nodo padre, mentre il figlio destro contiene un valore maggiore. Questa proprietà rende possibile la ricerca binaria, riducendo il numero di confronti necessari.
Questo articolo fa parte di una raccolta dedicata alla preparazione del concorso nella classe di concorso A41 dedicata all’insegnamento dell’informatica alle scuole superiori. Se cerchi altri articoli in merito, clicca qui!
Supporta EasyScience acquistando il prodotto tramite il nostro link! Ricorda: consigliamo solo prodotti che riteniamo validi e testati.
Se non conosci gli alberi in informatica, visita il nostro articolo.
Struttura e Proprietà di un Albero Binario di Ricerca
Un albero binario di ricerca è definito come segue:
- Ogni nodo contiene un valore, un riferimento al figlio sinistro e un riferimento al figlio destro.
- Per ogni nodo
n:- tutti i valori nel sotto-albero sinistro sono minori del valore di n.
- tutti i valori nel sotto-albero destro sono maggiori del valore di n.
Questa struttura permette di mantenere l’insieme di dati ordinato in modo che operazioni di ricerca, inserimento e cancellazione possano essere eseguite efficientemente.
Esempi
Supporta EasyScience acquistando il prodotto tramite il nostro link! Ricorda: consigliamo solo prodotti che riteniamo validi e testati.
Funzionamento della Ricerca
La ricerca in un albero binario di ricerca inizia dalla radice e segue il percorso determinato dai confronti tra il valore cercato e i valori dei nodi. Vediamo un esempio di applicazione della ricerca binaria nell’esempio di sopra.
Vogliamo cercare il valore 31 nell’albero.
Confronto con la radice:
- Il valore cercato (
31) è confrontato con il valore della radice (55). - Poiché
31è minore di55, ci spostiamo al figlio sinistro della radice.
Confronto con il nodo successivo:
- Ora,
31è confrontato con il valore del nodo corrente (40). - Poiché
40è maggiore di31, ci spostiamo al figlio sinistro del nodo corrente.
Confronto con il nodo successivo:
- Ora,
31è confrontato con il valore del nodo corrente (30). - Poiché
31è maggiore di30, ci spostiamo al figlio destro del nodo corrente.
Confronto con il nodo finale:
- Infine,
31è confrontato con il valore del nodo corrente (31). - Poiché
31è uguale a31, abbiamo trovato il valore cercato.
Il processo di ricerca è terminato con successo.
Per la ricerca dell’elemento massimo, basta partire dalla radice e percorrere sempre i sotto-alberi di destra. Per il minimo basta seguire sempre i sotto-alberi di sinistra.
Esempio in Java di un Albero Binario di Ricerca
Vediamo un esempio di implementazione di un albero binario di ricerca in Java, concentrandoci sull’operazione di ricerca.
class Node {
int value;
Node left, right;
public Node(int item) {
value = item;
left = right = null;
}
}
class BinarySearchTree {
Node root;
BinarySearchTree() {
root = null;
}
void insert(int value) {
root = insertRec(root, value);
}
Node insertRec(Node root, int value) {
if (root == null) {
root = new Node(value);
return root;
}
if (value < root.value)
root.left = insertRec(root.left, value);
else if (value > root.value)
root.right = insertRec(root.right, value);
return root;
}
boolean search(int value) {
return searchRec(root, value);
}
boolean searchRec(Node root, int value) {
if (root == null) {
return false;
}
if (root.value == value) {
return true;
}
if (root.value > value) {
return searchRec(root.left, value);
}
return searchRec(root.right, value);
}
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
bst.insert(50);
bst.insert(30);
bst.insert(20);
bst.insert(40);
bst.insert(70);
bst.insert(60);
bst.insert(80);
System.out.println(bst.search(40)); // Output: true
System.out.println(bst.search(90)); // Output: false
}
}Nell’esempio in Java, viene prima creato l’albero binario di ricerca con il metodo insert che inserisce in maniera ordinata gli elementi nell’albero poi viene eseguita la ricerca del nodo con il metodo search.
Complessità Computazionale della ricerca in albero binario di ricerca
La complessità computazionale delle operazioni di ricerca in un BST dipende dall’altezza dell’albero. La complessità computazione è \(O(h)\), dove \(h\) è l’altezza dell’albero. Nel caso migliore (l’albero binario è bilanciato) è \(O(log n)\).
Se non sai cos’è la complessità computazionale, visita il nostro articolo!
Supporta EasyScience acquistando il prodotto tramite il nostro link! Ricorda: consigliamo solo prodotti che riteniamo validi e testati.
Bibliografia
In questa pagina sono presenti link di affiliazione che garantiscono a questo sito una piccola quota di ricavi, senza variazione del prezzo per l'acquirente.
