Come funziona la ricerca nell'albero?

La ricerca in un albero dipende dalla sua struttura e dall'obiettivo della ricerca.

Principali metodi di ricerca:

1. Ricerca in profondità (DFS - Depth-First Search): Si approfondisce il più possibile in un ramo prima di passare a quello successivo. Viene implementata usando uno stack (esplicito o tramite ricorsione).

   • Visita pre-ordine: Visitare la radice, poi il sottoalbero sinistro, poi quello destro.
   • Visita in-order: Visitare il sottoalbero sinistro, poi la radice, poi il sottoalbero destro. Usato negli alberi binari di ricerca per ottenere una lista ordinata di elementi.
   • Visita post-ordine: Visitare il sottoalbero sinistro, poi quello destro, poi la radice.

2. Ricerca in ampiezza (BFS - Breadth-First Search): Esplora tutti i vicini del nodo corrente a un livello prima di passare al successivo. Viene implementata usando una coda.

Esempio di DFS (In-order) per un albero binario:

// TreeNode rappresenta un nodo di un albero binario
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal esegue una traversata inorder
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Chiamata ricorsiva per il sottoalbero sinistro
	result = append(result, InOrderTraversal(root.Left)...)
	// Visita il nodo corrente
	result = append(result, root.Val)
	// Chiamata ricorsiva per il sottoalbero destro
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

Esempio di BFS:

// TreeNode rappresenta un nodo di un albero binario
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal esegue una traversata BFS
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Coda per memorizzare i nodi al livello corrente
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// Estrae il primo elemento dalla coda
		node := queue[0]
		queue = queue[1:]

		// Aggiunge il valore del nodo ai risultati
		result = append(result, node.Val)

		// Aggiunge il figlio sinistro alla coda se esiste
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// Aggiunge il figlio destro alla coda se esiste
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

Per gli alberi binari di ricerca (BST), dove il sottoalbero sinistro è minore della radice e quello destro è maggiore:

3. Ricerca binaria: Quando si cerca un valore specifico, lo si confronta con la radice. Se il valore è minore, si cerca nel sottoalbero sinistro; se è maggiore, nel destro. Questa è la strategia più efficiente per la ricerca in BST.

// TreeNode rappresenta un nodo di un albero binario di ricerca
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST esegue una ricerca binaria in un BST
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // Nodo trovato o albero vuoto
	}

	if target < root.Val {
		// Ricerca nel sottoalbero sinistro
		return SearchBST(root.Left, target)
	}
	// Ricerca nel sottoalbero destro
	return SearchBST(root.Right, target)
}

La scelta dell'algoritmo di ricerca dipende dal compito e dalle caratteristiche dell'albero. DFS è adatto per compiti in cui è necessario percorrere profondamente un ramo o trovare un percorso verso un obiettivo. BFS è utile per trovare il percorso più breve o attraversare i livelli. La ricerca binaria è efficiente per trovare un valore specifico in strutture ordinate come il BST.