Ako funguje vyhľadávanie v strome?

Hľadanie v strome závisí od jeho štruktúry a cieľa hľadania.

Hlavné spôsoby hľadania:

Hľadanie do hĺbky (DFS - Depth-First Search): Ide maximálne do hĺbky jednej vetvy, než prejde na susednú. Implementuje sa pomocou zásobníka (explicitne alebo rekurziou).
- Predbežný prechod (Pre-order): Navštívi koreň, potom ľavé podstrom, potom pravé podstrom.
- In-order prechod: Navštívi ľavé podstrom, potom koreň, potom pravé podstrom. Používa sa na získanie zoradeného zoznamu prvkov v binárnych stromoch prehľadávania.
- Post-order: Navštívi ľavé podstrom, pravé podstrom, potom koreň.
Prehľadávanie do šírky (BFS - Breadth-First Search): Preskúma všetkých susedov na jednom úrovni pred prechodom na ďalšiu. Implementuje sa pomocou frontu.

Príklad DFS (In-order) pre binárny strom:

// TreeNode predstavuje uzol binárneho stromu
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal vykonáva inorder prechod
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Rekurzívny volanie pre ľavý podstrom
	result = append(result, InOrderTraversal(root.Left)...)
	// Návšteva aktuálneho uzla
	result = append(result, root.Val)
	// Rekurzívny volanie pre pravý podstrom
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

Príklad BFS:

// TreeNode predstavuje uzol binárneho stromu
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal vykonáva BFS prechod
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Fronta na uloženie uzlov na aktuálnej úrovni
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// Odstrániť prvý prvok z fronty
		node := queue[0]
		queue = queue[1:]

		// Pridať hodnotu uzla do výsledku
		result = append(result, node.Val)

		// Pridať ľavého potomka do fronty, ak existuje
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// Pridať pravého potomka do fronty, ak existuje
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

Pre binárne vyhľadávacie stromy (BST), kde je ľavé podstrom menší ako koreň a pravé väčšie:

Binárne vyhľadávanie: Pri hľadaní konkrétnej hodnoty ju porovnávame s koreňom. Ak je menšia, hľadáme v ľavom podstrome; ak je väčšia, v pravom. Toto je najefektívnejšia stratégia hľadania v BST.

// TreeNode predstavuje uzol binárneho stromu pre vyhľadávanie
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST vykonáva binárne vyhľadávanie v BST
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // Uzol nájdený alebo strom je prázdny
	}

	if target < root.Val {
		// Hľadanie v ľavom podstrome
		return SearchBST(root.Left, target)
	}
	// Hľadanie v pravom podstrome
	return SearchBST(root.Right, target)
}

Výber algoritmu závisí od úlohy a vlastností stromu. DFS je vhodný na prechádzanie do hĺbky alebo hľadanie cesty k cieľu. BFS je vhodný na nájdenie najkratšej cesty alebo prechádzanie po úrovniach. Binárne vyhľadávanie je efektívne na hľadanie konkrétnej hodnoty v zoradených štruktúrach, ako je BST.