Albero binario
Ultimo aggiornamento
Un albero binario è una gerarchia in cui ogni nodo ha al massimo due figli, chiamati figlio sinistro e figlio destro. Il nodo in cima è la radice, i nodi senza figli sono le foglie e il numero di archi dalla radice alla foglia più profonda è l'altezza dell'albero. A differenza di un albero binario di ricerca, un albero binario semplice non ha regole di ordine: è solo la forma. Premi play qui sopra per vedere un albero riempirsi livello per livello e poi essere visitato in ordine (sinistra, nodo, destra).
Gli alberi binari sono alla base di molte strutture: alberi binari di ricerca, heap, alberi delle espressioni e altro. Le visite passano per ogni nodo in un ordine definito: in ordine, in pre-ordine e in post-ordine sono le tre visite in profondità, ognuna utile per compiti diversi.
Terminologia
| Termine | Significato |
|---|---|
| Radice | Il nodo in cima, senza genitore |
| Foglia | Un nodo senza figli |
| Altezza | Il percorso più lungo dalla radice a una foglia (in archi) |
| Profondità | Distanza di un nodo dalla radice |
| Completo | Tutti i livelli pieni tranne forse l'ultimo, riempito da sinistra a destra |
Le tre visite in profondità
| Visita | Ordine | Uso comune |
|---|---|---|
| In ordine | Sinistra, nodo, destra | Output ordinato di un BST |
| Pre-ordine | Nodo, sinistra, destra | Copiare / serializzare un albero |
| Post-ordine | Sinistra, destra, nodo | Eliminare / valutare un albero |
Esempio svolto
Visita in ordine dell'albero costruito da [4, 2, 6, 1, 3, 5] (riempito livello per livello):
| Passo | Nel nodo | Azione |
|---|---|---|
| 1 | 4 | Scendi ricorsivamente nel sottoalbero sinistro di 4 prima di visitarlo |
| 2 | 2 | Scendi ricorsivamente nel sottoalbero sinistro di 2 prima di visitarlo |
| 3 | 1 | Foglia, nessun figlio sinistro: visita 1, output [1] |
| 4 | 2 | Sinistra completata: visita 2, output [1, 2], poi scendi a destra |
| 5 | 3 | Foglia: visita 3, output [1, 2, 3] |
| 6 | 4 | Sottoalbero sinistro completato: visita 4, output [1, 2, 3, 4], poi scendi a destra |
| 7 | 5 | Figlio sinistro di 6, una foglia: visita 5, output [1, 2, 3, 4, 5] |
| 8 | 6 | Sinistra completata, nessun figlio destro: visita 6, output [1, 2, 3, 4, 5, 6] |
Quando usare un albero binario
| Usalo quando | Evitalo quando |
|---|---|
| Devi modellare dati intrinsecamente gerarchici (file system, alberi delle espressioni, DOM) | I dati sono piatti e basterebbe una lista o un array: un albero aggiunge solo overhead |
| Vuoi operazioni ordinate e puoi mantenerlo bilanciato (un BST o un albero autobilanciato) | Ti serve una ricerca per chiave O(1) in media: una tabella hash batte qualsiasi albero |
| Ti serve elaborare dati strutturati in ordine, in pre-ordine o in post-ordine | I nodi vengono inseriti in ordine in un BST non bilanciato: degrada a una lista O(n) |
| Contano le query su intervalli o l'iterazione ordinata, che le tabelle hash non offrono | La memoria è poca: ogni nodo porta due puntatori ai figli oltre al dato |
Codice Binary Tree
Un'implementazione di Binary 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 Tree in Python
Python
1from collections import deque2
3
4class Node:5 def __init__(self, value):6 self.value = value7 self.left = None8 self.right = None9
10
11def insert(root, value):12 # Level-order insert: fill the first empty child slot found13 if root is None:14 return Node(value)15 queue = deque([root])16 while queue:17 node = queue.popleft()18 if node.left is None:19 node.left = Node(value)20 return root21 queue.append(node.left)22 if node.right is None:23 node.right = Node(value)24 return root25 queue.append(node.right)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.value] + inorder(node.right)32
33
34root = None35for value in [1, 2, 3, 4, 5, 6, 7]:36 root = insert(root, value)37
38print("Root: ", root.value)39print("Inorder:", inorder(root))Codice Binary 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 BinaryTree {10 constructor() {11 this.root = null;12 }13
14 // Insert at the first free spot, top to bottom (level order)15 insert(value) {16 const node = new Node(value);17 if (!this.root) {18 this.root = node;19 return;20 }21 const queue = [this.root];22 while (queue.length > 0) {23 const current = queue.shift();24 if (!current.left) {25 current.left = node;26 return;27 }28 if (!current.right) {29 current.right = node;30 return;31 }32 queue.push(current.left, current.right);33 }34 }35
36 inorder(node = this.root, out = []) {37 if (!node) return out;38 this.inorder(node.left, out);39 out.push(node.value);40 this.inorder(node.right, out);41 return out;42 }43}44
45const tree = new BinaryTree();46for (const value of [1, 2, 3, 4, 5, 6, 7]) tree.insert(value);47console.log("Inorder traversal:", tree.inorder().join(" "));Codice Binary Tree in Java
Java
1import java.util.ArrayDeque;2import java.util.Queue;3
4public class Main {5 static class Node {6 int value;7 Node left, right;8 Node(int value) { this.value = value; }9 }10
11 static Node root;12
13 // Insert at the first free slot in level order (keeps the tree complete)14 static void insert(int value) {15 Node node = new Node(value);16 if (root == null) { root = node; return; }17 Queue<Node> queue = new ArrayDeque<>();18 queue.add(root);19 while (!queue.isEmpty()) {20 Node cur = queue.poll();21 if (cur.left == null) { cur.left = node; return; }22 if (cur.right == null) { cur.right = node; return; }23 queue.add(cur.left);24 queue.add(cur.right);25 }26 }27
28 // Inorder: left subtree, node, right subtree29 static void inorder(Node node, StringBuilder sb) {30 if (node == null) return;31 inorder(node.left, sb);32 sb.append(node.value).append(" ");33 inorder(node.right, sb);34 }35
36 public static void main(String[] args) {37 for (int v = 1; v <= 7; v++) insert(v);38 StringBuilder sb = new StringBuilder();39 inorder(root, sb);40 System.out.println("Root: " + root.value);41 System.out.println("Inorder: " + sb.toString().trim());42 }43}Codice Binary 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 root->right = insert(root->right, value);14 return root;15}16
17// In-order traversal: left subtree, node, right subtree18void inorder(const Node* node) {19 if (node == nullptr) return;20 inorder(node->left);21 std::cout << node->value << " ";22 inorder(node->right);23}24
25int countNodes(const Node* node) {26 if (node == nullptr) return 0;27 return 1 + countNodes(node->left) + countNodes(node->right);28}29
30int main() {31 Node* root = nullptr;32 for (int value : {8, 3, 10, 1, 6, 14, 4}) {33 root = insert(root, value);34 }35 std::cout << "In-order: ";36 inorder(root);37 std::cout << "\n";38 std::cout << "Node count: " << countNodes(root) << "\n";39 return 0;40}Codice Binary Tree in C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value;6 struct Node* left;7 struct Node* right;8} Node;9
10Node* newNode(int value) {11 Node* n = malloc(sizeof(Node));12 n->value = value;13 n->left = n->right = NULL;14 return n;15}16
17Node* insert(Node* root, int value) {18 if (root == NULL) return newNode(value);19 if (value < root->value) root->left = insert(root->left, value);20 else root->right = insert(root->right, value);21 return root;22}23
24// In-order traversal: left subtree, node, right subtree25void inorder(const Node* node) {26 if (node == NULL) return;27 inorder(node->left);28 printf("%d ", node->value);29 inorder(node->right);30}31
32int countNodes(const Node* node) {33 if (node == NULL) return 0;34 return 1 + countNodes(node->left) + countNodes(node->right);35}36
37int main(void) {38 int values[] = {8, 3, 10, 1, 6, 14, 4};39 Node* root = NULL;40 for (int i = 0; i < 7; i++) root = insert(root, values[i]);41 printf("In-order: ");42 inorder(root);43 printf("\n");44 printf("Node count: %d\n", countNodes(root));45 return 0;46}Domande frequenti sull'albero binario
Qual è la differenza tra un albero binario e un albero binario di ricerca?
Un albero binario limita semplicemente ogni nodo ad avere al massimo due figli, senza ordine. Un albero binario di ricerca aggiunge la regola per cui tutto ciò che sta nel sottoalbero sinistro è più piccolo e tutto ciò che sta nel sottoalbero destro è più grande, ed è questo che rende veloce la ricerca.
Cos'è una visita in ordine?
La visita in ordine visita il sottoalbero sinistro, poi il nodo, poi il sottoalbero destro, in modo ricorsivo. Per un albero binario di ricerca produce i valori in ordine crescente, ed è per questo che è la visita più usata negli esempi.
Cos'è un albero binario completo?
Un albero binario completo ha tutti i livelli pieni tranne forse l'ultimo, che viene riempito da sinistra a destra. Questa forma permette di memorizzare l'albero in modo compatto in un array (senza puntatori ai figli), ed è così che si implementano gli heap binari.
Quando conviene usare un albero binario invece di un array o di una tabella hash?
Scegli un albero quando i tuoi dati sono naturalmente gerarchici o quando ti servono operazioni ordinate come query su intervalli e iterazione ordinata, che le tabelle hash non ti danno. Se ti serve solo una ricerca veloce per chiave senza ordine, l'accesso
O(1) in media di una tabella hash batte un albero, e per dati piatti un array è più semplice e sfrutta meglio la cache.Qual è la differenza tra altezza e profondità di un albero binario?
La profondità si misura dalla radice verso un nodo specifico: è il numero di archi sul percorso dalla radice a quel nodo. L'altezza si misura da un nodo verso la sua foglia più profonda, quindi l'altezza dell'intero albero è la profondità del suo nodo più profondo. Un albero con un solo nodo ha altezza
0 e il suo unico nodo ha anche profondità 0.Perché un albero binario non bilanciato ha prestazioni così scarse?
Ricerca, inserimento ed eliminazione in un albero binario di ricerca costano
O(h), dove h è l'altezza. Quando le chiavi vengono inserite in ordine, l'albero diventa una linea retta, quindi h cresce fino a n e ogni operazione degrada a O(n), non meglio di una lista concatenata. Gli alberi autobilanciati come gli AVL o i rosso-neri mantengono l'altezza a O(log n) per evitarlo.Risorse correlate
Altre visualizzazioni
