1. Che cos'è un Binary Search Tree (BST)?

Un Albero Binario di Ricerca (Binary Search Tree o BST) è un albero binario che rispetta una rigorosa proprietà di ordinamento in ogni suo nodo:

• Il valore memorizzato nel sottoalbero sinistro di un nodo è minore del valore del nodo stesso.
• Il valore memorizzato nel sottoalbero destro di un nodo è maggiore o uguale al valore del nodo stesso.
• Anche tutti i sottoalberi sinistro e destro sono a loro volta, per definizione, dei BST.

2. Vantaggi e Complessità

Grazie alla struttura ordinata, le operazioni di ricerca, inserimento e cancellazione in un BST bilanciato presentano una complessità temporale logaritmica pari a $\mathcal{O}(\log N)$, decisamente più efficiente rispetto alla ricerca lineare su vettori non ordinati ($\mathcal{O}(N)$).

3. Strategie di Visita dell'Albero

Per attraversare o stampare tutti i nodi di un albero binario si utilizzano tre principali modalità ricorsive:

• In-order (Simmetrica): Visita il sottoalbero sinistro, elabora la radice, visita il sottoalbero destro. Nel BST restituisce i valori ordinati in modo crescente.
• Pre-order (Anticipata): Elabora prima la radice, poi visita il sottoalbero sinistro e infine il destro.
• Post-order (Posticipata): Visita prima il sottoalbero sinistro, poi il destro e infine elabora la radice.

4. Simulatore Interattivo: Inserimento in un BST

Digita un valore numerico da inserire nel BST: il simulatore verificherà la regola di posizionamento.