Albero binario di ricerca (BST)
Ultimo aggiornamento
Un albero binario di ricerca mantiene i valori in ordine: per ogni nodo, tutti i valori del sottoalbero sinistro sono più piccoli e tutti quelli del sottoalbero destro sono più grandi. Per inserire o trovare un valore parti dalla radice e scendi ripetutamente a sinistra o a destra in base al confronto, così ogni passo dimezza lo spazio di ricerca. Premi play qui sopra per vedere i valori collocati per confronto e una ricerca che scende lungo l'albero.
Su un albero bilanciato queste operazioni richiedono tempo O(log n). Il problema: inserire dati già ordinati fa degenerare l'albero in una lista concatenata con operazioni O(n), ed è proprio per questo che esistono varianti autobilanciate come gli alberi AVL e rosso-neri.
Complessità temporale e spaziale
| Operazione | Bilanciato | Caso peggiore (sbilanciato) |
|---|---|---|
| Ricerca | O(log n) | O(n) |
| Inserimento | O(log n) | O(n) |
| Eliminazione | O(log n) | O(n) |
| Spazio | O(n) | O(n) |
Passo dopo passo (inserimento)
| Passo | Cosa succede |
|---|---|
| 1 | Se l'albero è vuoto, il nuovo valore diventa la radice. |
| 2 | Altrimenti parti dalla radice. |
| 3 | Se il valore è più piccolo, vai al figlio sinistro; se è più grande, vai a destra. |
| 4 | Ripeti finché non raggiungi un posto vuoto. |
| 5 | Aggancia lì il nuovo valore come foglia. |
Esempio svolto
Inserimento di [5, 3, 8, 1, 4] in un albero vuoto, un valore alla volta:
| Inserimento | Percorso seguito | Azione |
|---|---|---|
5 | - | L'albero è vuoto, quindi 5 diventa la radice. |
3 | 5 | 3 < 5, vai a sinistra; il posto è vuoto, aggancia 3 come figlio sinistro di 5. |
8 | 5 | 8 > 5, vai a destra; il posto è vuoto, aggancia 8 come figlio destro di 5. |
1 | 5 -> 3 | 1 < 5 vai a sinistra, poi 1 < 3 vai a sinistra; aggancia 1 come figlio sinistro di 3. |
4 | 5 -> 3 | 4 < 5 vai a sinistra, poi 4 > 3 vai a destra; aggancia 4 come figlio destro di 3. |
Quando usare un albero binario di ricerca
| Usalo quando | Evitalo quando |
|---|---|
| Ti servono l'ordinamento e ricerche veloci, e gli inserimenti arrivano in ordine casuale. | I tuoi dati arrivano già ordinati: un BST non bilanciato degrada a O(n) per operazione. |
| Vuoi che la visita in ordine restituisca i valori in sequenza ordinata senza costi extra. | Ti servono solo test di appartenenza senza ordine: una tabella hash dà ricerche O(1) in media. |
| Ti servono query su intervalli o il successore/predecessore di una chiave. | Ti servono limiti O(log n) garantiti: scegli piuttosto un albero AVL o rosso-nero autobilanciato. |
| L'insieme di dati cambia spesso e un array ordinato statico sarebbe costoso da aggiornare. | L'insieme di dati è fisso e di sola lettura: un array ordinato con ricerca binaria è più semplice e sfrutta meglio la cache. |
Codice Binary Search Tree
Un'implementazione di Binary Search Tree pulita ed eseguibile in Python, JavaScript, Java, C++, C. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice Binary Search Tree in Python
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6
7
8def insert(node, key):9 if node is None:10 return Node(key)11 if key < node.key:12 node.left = insert(node.left, key)13 elif key > node.key:14 node.right = insert(node.right, key)15 return node # duplicates are ignored16
17
18def search(node, key):19 if node is None:20 return False21 if key == node.key:22 return True23 if key < node.key:24 return search(node.left, key)25 return search(node.right, key)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.key] + inorder(node.right)32
33
34root = None35for key in [8, 3, 10, 1, 6, 14, 4, 7]:36 root = insert(root, key)37
38print("Inorder (sorted):", inorder(root))39print("search(6): ", search(root, 6))40print("search(5): ", search(root, 5))Codice Binary Search Tree in JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7}8
9class BinarySearchTree {10 constructor() {11 this.root = null;12 }13
14 insert(value) {15 const attach = (node) => {16 if (!node) return new Node(value);17 if (value < node.value) node.left = attach(node.left);18 else node.right = attach(node.right);19 return node;20 };21 this.root = attach(this.root);22 }23
24 search(value) {25 let current = this.root;26 while (current) {27 if (value === current.value) return true;28 current = value < current.value ? current.left : current.right;29 }30 return false;31 }32
33 // Inorder traversal of a BST visits values in sorted order34 inorder(node = this.root, out = []) {35 if (!node) return out;36 this.inorder(node.left, out);37 out.push(node.value);38 this.inorder(node.right, out);39 return out;40 }41}42
43const bst = new BinarySearchTree();44for (const value of [8, 3, 10, 1, 6, 14, 4]) bst.insert(value);45console.log("Inorder:", bst.inorder().join(" "));46console.log("search(6):", bst.search(6));47console.log("search(7):", bst.search(7));Codice Binary Search Tree in Java
Java
1public class Main {2 static class Node {3 int key;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static Node insert(Node node, int key) {9 if (node == null) return new Node(key);10 // Smaller keys go left, larger keys go right11 if (key < node.key) node.left = insert(node.left, key);12 else if (key > node.key) node.right = insert(node.right, key);13 return node;14 }15
16 static boolean search(Node node, int key) {17 if (node == null) return false;18 if (key == node.key) return true;19 return key < node.key ? search(node.left, key) : search(node.right, key);20 }21
22 static void inorder(Node node, StringBuilder sb) {23 if (node == null) return;24 inorder(node.left, sb);25 sb.append(node.key).append(" ");26 inorder(node.right, sb);27 }28
29 public static void main(String[] args) {30 Node root = null;31 int[] keys = {8, 3, 10, 1, 6, 14, 4};32 for (int k : keys) root = insert(root, k);33
34 StringBuilder sb = new StringBuilder();35 inorder(root, sb);36 System.out.println("Inorder (sorted): " + sb.toString().trim());37 System.out.println("search 6: " + search(root, 6));38 System.out.println("search 7: " + search(root, 7));39 }40}Codice Binary Search Tree in C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* left = nullptr;6 Node* right = nullptr;7 explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11 if (root == nullptr) return new Node(value);12 if (value < root->value) root->left = insert(root->left, value);13 else if (value > root->value) root->right = insert(root->right, value);14 return root; // duplicates are ignored15}16
17bool contains(const Node* root, int value) {18 // Walk down: smaller goes left, larger goes right19 while (root != nullptr) {20 if (value == root->value) return true;21 root = value < root->value ? root->left : root->right;22 }23 return false;24}25
26void inorder(const Node* node) {27 if (node == nullptr) return;28 inorder(node->left);29 std::cout << node->value << " ";30 inorder(node->right);31}32
33int main() {34 Node* root = nullptr;35 for (int value : {50, 30, 70, 20, 40, 60, 80}) {36 root = insert(root, value);37 }38 std::cout << "Sorted: ";39 inorder(root);40 std::cout << "\n" << std::boolalpha;41 std::cout << "contains(40): " << contains(root, 40) << "\n";42 std::cout << "contains(45): " << contains(root, 45) << "\n";43 return 0;44}Codice Binary Search Tree in C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* left;8 struct Node* right;9} Node;10
11Node* newNode(int value) {12 Node* n = malloc(sizeof(Node));13 n->value = value;14 n->left = n->right = NULL;15 return n;16}17
18Node* insert(Node* root, int value) {19 if (root == NULL) return newNode(value);20 if (value < root->value) root->left = insert(root->left, value);21 else if (value > root->value) root->right = insert(root->right, value);22 return root; // duplicates are ignored23}24
25bool contains(const Node* root, int value) {26 // Walk down: smaller goes left, larger goes right27 while (root != NULL) {28 if (value == root->value) return true;29 root = value < root->value ? root->left : root->right;30 }31 return false;32}33
34void inorder(const Node* node) {35 if (node == NULL) return;36 inorder(node->left);37 printf("%d ", node->value);38 inorder(node->right);39}40
41int main(void) {42 int values[] = {50, 30, 70, 20, 40, 60, 80};43 Node* root = NULL;44 for (int i = 0; i < 7; i++) root = insert(root, values[i]);45 printf("Sorted: ");46 inorder(root);47 printf("\n");48 printf("contains(40): %s\n", contains(root, 40) ? "true" : "false");49 printf("contains(45): %s\n", contains(root, 45) ? "true" : "false");50 return 0;51}Domande frequenti sull'albero binario di ricerca
Qual è la complessità temporale di un albero binario di ricerca?
Ricerca, inserimento ed eliminazione sono
O(log n) su un albero bilanciato, perché ogni confronto scarta metà dei nodi rimasti. Nel caso peggiore, un albero ridotto a una catena da inserimenti ordinati, degradano a O(n).Qual è la differenza tra un albero binario e un albero binario di ricerca?
Un albero binario è qualsiasi albero in cui ogni nodo ha al massimo due figli, senza regole di ordine. Un albero binario di ricerca aggiunge l'invariante per cui i valori del sottoalbero sinistro sono più piccoli e quelli del sottoalbero destro più grandi del nodo, ed è questo che rende possibile la ricerca veloce.
Perché un albero binario di ricerca può diventare lento?
Se i valori vengono inseriti in ordine (crescente o decrescente), ogni nuovo nodo finisce dallo stesso lato, producendo un albero alto e sbilanciato che si comporta come una lista concatenata:
O(n) per operazione. Gli alberi autobilanciati (AVL, rosso-neri) ruotano i nodi per evitarlo.Qual è la differenza tra un albero binario di ricerca e una tabella hash?
Una tabella hash dà ricerche
O(1) in media ma non conserva le chiavi in un ordine particolare, quindi non può rispondere a query su intervalli o sul successore. Un albero binario di ricerca è un po' più lento, O(log n), ma mantiene le chiavi ordinate, così puoi scorrerle in ordine e trovare i valori più vicini. Scegli un BST quando l'ordine conta e una tabella hash quando ti servono solo test di appartenenza.Quando conviene usare un albero autobilanciato invece di un BST semplice?
Usa un albero autobilanciato (AVL, rosso-nero) ogni volta che non puoi controllare l'ordine di inserimento e ti servono prestazioni
O(log n) garantite. Un BST semplice va bene per imparare, per insiemi di dati piccoli o quando le chiavi arrivano in ordine casuale, ma non offre protezione contro il caso peggiore sbilanciato.La visita in ordine di un BST restituisce valori ordinati?
Sì. Visitare il sottoalbero sinistro, poi il nodo, poi il sottoalbero destro restituisce le chiavi in ordine crescente, come conseguenza diretta dell'invariante del BST. Un errore comune è aspettarsi lo stesso da un albero binario semplice: senza la regola di ordine, la visita in ordine non produce una sequenza significativa.
Risorse correlate
Altre visualizzazioni
