Jak funguje hledání v stromu?

Hledání v stromu závisí na jeho struktuře a cíli hledání.

Hlavní způsoby hledání:

Hledání do hloubky (DFS - Depth-First Search): Jde maximálně do hloubky jednoho větve, než přejde k sousední. Implementuje se pomocí zásobníku (explicitně nebo rekurzí).
- Předběžný průchod (Pre-order): Navštívit kořen, poté levý podstrom, poté pravý podstrom.
- In-order průchod: Navštívit levý podstrom, pak kořen, pak pravý podstrom. Používá se u binárních vyhledávacích stromů pro získání seřazeného seznamu prvků.
- Post-order: Navštívit levý podstrom, pravý podstrom, pak kořen.
Hledání do šířky (BFS - Breadth-First Search): Prozkoumá všechny sousedy na jedné úrovni před přechodem na další. Implementuje se pomocí fronty.

Příklad DFS (In-order) pro binární strom:

// TreeNode představuje uzel binárního stromu
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal provádí inorder průchod
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Rekurzivní volání pro levé podstrom
	result = append(result, InOrderTraversal(root.Left)...)
	// Návštěva aktuálního uzlu
	result = append(result, root.Val)
	// Rekurzivní volání pro pravé podstrom
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

Příklad BFS:

// TreeNode představuje uzel binárního stromu
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal provádí BFS průchod
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Fronta pro uložení uzlů na aktuální úrovni
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// Odebrat první prvek z fronty
		node := queue[0]
		queue = queue[1:]

		// Přidat hodnotu uzlu do výsledku
		result = append(result, node.Val)

		// Přidat levého potomka do fronty, pokud existuje
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// Přidat pravého potomka do fronty, pokud existuje
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

Pro binární vyhledávací stromy (BST), kde levé podstrom je menší než kořen a pravé větší:

Binární hledání: Při hledání konkrétní hodnoty ji porovnáváme s kořenem. Pokud je menší, hledáme v levém podstromu; pokud je větší, v pravém. Toto je nejefektivnější strategie hledání v BST.

// TreeNode představuje uzel binárního vyhledávacího stromu
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST provádí binární hledání v BST
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // Uzlík nalezen nebo strom je prázdný
	}

	if target < root.Val {
		// Hledat v levém podstromu
		return SearchBST(root.Left, target)
	}
	// Hledat v pravém podstromu
	return SearchBST(root.Right, target)
}

Volba algoritmu hledání závisí na úloze a vlastnostech stromu. DFS je vhodný pro případy, kdy je třeba jít hluboko do větve nebo najít cestu k cíli. BFS je vhodný pro hledání nejkratší cesty nebo průchod úrovněmi. Binární hledání je efektivní pro hledání konkrétní hodnoty v seřazených strukturách, jako je BST.