Jak działa wyszukiwanie w drzewie?

Wyszukiwanie w drzewie zależy od jego struktury i celu wyszukiwania.

Główne metody wyszukiwania:

Przeszukiwanie wg głębokości (DFS - Depth-First Search): Idzie maksymalnie głęboko w jednym odgałęzieniu, zanim przejdzie do następnego. Implementuje się je za pomocą stosu (jawnie lub niejawnie przez rekurencję).
- Przeszukiwanie wstępne (Pre-order): Odwiedzić korzeń, następnie lewy poddrzewo, potem prawe.
- Przeszukiwanie in-order: Odwiedzić lewe poddrzewo, potem korzeń, potem prawe poddrzewo. Używane w drzewach binarnych wyszukiwania do uzyskania posortowanej listy elementów.
- Przeszukiwanie post-order: Odwiedzić lewe poddrzewo, potem prawe, potem korzeń.
Przeszukiwanie wszerz (BFS - Breadth-First Search): Eksploruje wszystkich sąsiadów bieżącego węzła na jednym poziomie, zanim przejdzie do następnego. Implementuje się je za pomocą kolejki.

Przykład DFS (in-order) dla drzewa binarnego:

// TreeNode reprezentuje węzeł drzewa binarnego
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal wykonuje przejście in-order
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Rekurencyjne wywołanie dla lewego poddrzewa
	result = append(result, InOrderTraversal(root.Left)...)
	// Odwiedzenie bieżącego węzła
	result = append(result, root.Val)
	// Rekurencyjne wywołanie dla prawego poddrzewa
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

Przykład BFS:

// TreeNode reprezentuje węzeł drzewa binarnego
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal wykonuje przejście BFS
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Kolejka do przechowywania węzłów na bieżącym poziomie
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// Usunięcie pierwszego elementu z kolejki
		node := queue[0]
		queue = queue[1:]

		// Dodanie wartości węzła do wyniku
		result = append(result, node.Val)

		// Dodanie lewego dziecka do kolejki, jeśli istnieje
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// Dodanie prawego dziecka do kolejki, jeśli istnieje
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

Dla drzew binarnych wyszukiwania (BST), gdzie lewe poddrzewo jest mniejsze od korzenia, a prawe większe:

Wyszukiwanie binarne: Podczas wyszukiwania konkretnej wartości porównujemy ją z korzeniem. Jeśli jest mniejsza, szukamy w lewym poddrzewie; jeśli większa, w prawym. To najefektywniejsza strategia wyszukiwania w BST.

// TreeNode reprezentuje węzeł drzewa binarnego wyszukiwania
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST wykonuje wyszukiwanie binarne w BST
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // Węzeł znaleziony lub drzewo puste
	}

	if target < root.Val {
		// Szukanie w lewym poddrzewie
		return SearchBST(root.Left, target)
	}
	// Szukanie w prawym poddrzewie
	return SearchBST(root.Right, target)
}

Wybór algorytmu wyszukiwania zależy od zadania i cech drzewa. DFS nadaje się do zadań, gdzie trzeba głęboko przejść w jednym odgałęzieniu lub znaleźć ścieżkę do celu. BFS jest odpowiedni do znajdowania najkrótszej ścieżki lub przeszukiwania poziomami. Wyszukiwanie binarne jest skuteczne w poszukiwaniu konkretnej wartości w uporządkowanych strukturach, takich jak BST.