Un Binary Search Tree (BST) è una struttura dati ad albero in cui ogni nodo ha al massimo due figli
e soddisfa la seguente proprietà: per ogni nodo, tutti i valori nel sottoalbero sinistro sono minori del valore
del nodo, e tutti i valori nel sottoalbero destro sono maggiori. Questa struttura permette operazioni di ricerca,
inserimento e cancellazione in tempo medio O(log n), rendendola molto utile per gestire insiemi ordinati di dati.
Struttura di base di un nodo BST in Go
In Go possiamo rappresentare un nodo di un BST tramite una struct che contiene il valore e i puntatori ai figli sinistro e destro.
package bst
type Node struct {
Value int
Left *Node
Right *Node
}
In questo esempio il BST memorizza interi, ma nulla vieta di usare tipi generici (con Go 1.18+) o di memorizzare altri tipi associando una funzione di confronto.
Creare un nuovo albero
Possiamo rappresentare l'albero stesso come un puntatore al nodo radice. Un albero vuoto è semplicemente
un puntatore nil.
type Tree struct {
Root *Node
}
func NewTree() *Tree {
return &Tree{}
}
Inserimento di un valore nel BST
L'inserimento in un BST segue direttamente la proprietà dell'albero: se il valore da inserire è minore
del valore del nodo corrente, scendiamo a sinistra; se è maggiore, scendiamo a destra. Quando incontriamo un
puntatore nil, creiamo un nuovo nodo.
func (t *Tree) Insert(value int) {
t.Root = insertNode(t.Root, value)
}
func insertNode(n *Node, value int) *Node {
if n == nil {
return &Node{Value: value}
}
if value < n.Value {
n.Left = insertNode(n.Left, value)
} else if value > n.Value {
n.Right = insertNode(n.Right, value)
}
// Se value == n.Value non inseriamo duplicati (scelta progettuale)
return n
}
Nell'implementazione precedente, la funzione insertNode è ricorsiva. Notare che gestiamo i
duplicati semplicemente ignorando l'inserimento se il valore è già presente. A seconda delle esigenze, si
potrebbe decidere di contare le occorrenze o di inserire comunque i duplicati in uno dei sottoalberi.
Ricerca di un valore
La ricerca sfrutta ancora una volta la natura ordinata del BST: confrontiamo il valore cercato con il valore del nodo corrente e ci spostiamo a sinistra o a destra a seconda del risultato.
func (t *Tree) Search(value int) *Node {
return searchNode(t.Root, value)
}
func searchNode(n *Node, value int) *Node {
if n == nil {
return nil
}
if value == n.Value {
return n
}
if value < n.Value {
return searchNode(n.Left, value)
}
return searchNode(n.Right, value)
}
La funzione restituisce un puntatore al nodo che contiene il valore cercato oppure nil se il valore
non è presente nell'albero.
Visite dell'albero (traversal)
Esistono vari modi per visitare tutti i nodi di un BST. I più comuni sono:
- In-order: sinistra, nodo, destra (restituisce i valori in ordine crescente).
- Pre-order: nodo, sinistra, destra.
- Post-order: sinistra, destra, nodo.
Visita in-order
func (t *Tree) InOrder(visit func(int)) {
inOrder(t.Root, visit)
}
func inOrder(n *Node, visit func(int)) {
if n == nil {
return
}
inOrder(n.Left, visit)
visit(n.Value)
inOrder(n.Right, visit)
}
La funzione visit è una funzione di callback chiamata per ogni valore. Questo pattern permette di
riusare la logica di traversal in diversi contesti (stampa, accumulo in uno slice, calcoli, ecc.).
Visite pre-order e post-order
func (t *Tree) PreOrder(visit func(int)) {
preOrder(t.Root, visit)
}
func preOrder(n *Node, visit func(int)) {
if n == nil {
return
}
visit(n.Value)
preOrder(n.Left, visit)
preOrder(n.Right, visit)
}
func (t *Tree) PostOrder(visit func(int)) {
postOrder(t.Root, visit)
}
func postOrder(n *Node, visit func(int)) {
if n == nil {
return
}
postOrder(n.Left, visit)
postOrder(n.Right, visit)
visit(n.Value)
}
Cancellazione di un valore
La cancellazione è l'operazione più delicata in un BST, perché dobbiamo mantenere la proprietà dell'albero.
Ci sono tre casi principali quando vogliamo eliminare un nodo con valore value:
- Nodo foglia (senza figli): basta rimuoverlo.
- Nodo con un solo figlio: rimpiazziamo il nodo con il suo unico figlio.
- Nodo con due figli: troviamo il successore in-order (il minimo nel sottoalbero destro), copiamo il suo valore nel nodo da eliminare e poi cancelliamo il successore.
func (t *Tree) Delete(value int) {
t.Root = deleteNode(t.Root, value)
}
func deleteNode(n *Node, value int) *Node {
if n == nil {
return nil
}
if value < n.Value {
n.Left = deleteNode(n.Left, value)
return n
}
if value > n.Value {
n.Right = deleteNode(n.Right, value)
return n
}
// Caso 1: nessun figlio
if n.Left == nil && n.Right == nil {
return nil
}
// Caso 2: un solo figlio
if n.Left == nil {
return n.Right
}
if n.Right == nil {
return n.Left
}
// Caso 3: due figli
// Trova il minimo nel sottoalbero destro (successore in-order)
minRight := findMin(n.Right)
n.Value = minRight.Value
n.Right = deleteNode(n.Right, minRight.Value)
return n
}
func findMin(n *Node) *Node {
current := n
for current.Left != nil {
current = current.Left
}
return current
}
Con questa implementazione la proprietà di ricerca del BST viene mantenuta dopo ogni cancellazione.
Esempio completo di utilizzo
Vediamo ora un esempio completo in un package main che utilizza il BST definito sopra.
package main
import (
"fmt"
"example.com/bst"
)
func main() {
tree := bst.NewTree()
values := []int{8, 3, 10, 1, 6, 14, 4, 7, 13}
for _, v := range values {
tree.Insert(v)
}
fmt.Print("In-order: ")
tree.InOrder(func(v int) {
fmt.Printf("%d ", v)
})
fmt.Println()
fmt.Println("Search 6:", tree.Search(6) != nil)
fmt.Println("Search 2:", tree.Search(2) != nil)
tree.Delete(3)
fmt.Print("In-order dopo Delete(3): ")
tree.InOrder(func(v int) {
fmt.Printf("%d ", v)
})
fmt.Println()
}
In questo esempio:
- Creiamo un nuovo albero.
- Inseriamo una serie di valori.
- Stampiamo l'albero in ordine crescente.
- Verifichiamo la presenza di alcuni valori tramite
Search. - Cancelliamo il nodo con valore 3 e ristampiamo l'albero.
Considerazioni sulle prestazioni
Le prestazioni di un BST dipendono fortemente dalla sua forma. Nel caso migliore, quando l'albero è bilanciato,
la profondità è dell'ordine di log n e quindi ricerca, inserimento e cancellazione hanno complessità
media O(log n). Tuttavia, nel caso peggiore (dati già ordinati inseriti in sequenza) l'albero si
degrada in una lista collegata e le operazioni diventano O(n).
Per mitigare questo problema, in applicazioni reali si utilizzano spesso varianti bilanciate del BST, come gli alberi AVL o i Red-Black Tree. Tuttavia, comprendere il BST semplice è un passo fondamentale per capire queste strutture più avanzate.
Uso di generics per un BST più flessibile
Con l'introduzione dei generics in Go 1.18, è possibile definire un BST parametrico sul tipo di valore memorizzato. Questo permette di riutilizzare la stessa struttura per interi, stringhe o tipi custom, purché si definisca una funzione di confronto.
type Ordered interface {
~int | ~int64 | ~float64 | ~string
}
type GenericNode[T Ordered] struct {
Value T
Left *GenericNode[T]
Right *GenericNode[T]
}
Le funzioni di inserimento, ricerca e cancellazione sarebbero analoghe a quelle viste per il tipo int,
ma con il tipo generico T. Questo approccio rende il codice più riutilizzabile e pulito.
Conclusione
In questo articolo abbiamo visto come definire, creare e gestire un Binary Search Tree in Go, implementando le operazioni fondamentali: inserimento, ricerca, visite e cancellazione. Abbiamo inoltre discusso le prestazioni e accennato all'uso dei generics per rendere il BST più flessibile.
Il BST rimane una delle strutture dati di base più importanti e comprenderlo a fondo è essenziale per affrontare strutture più complesse e algoritmi avanzati. Partendo da queste basi, puoi estendere l'implementazione per supportare bilanciamento automatico, iterazione iterativa, serializzazione e molte altre funzionalità.