Hogyan működik a keresés a fában?

A fa keresése az szerkezetétől és a keresés céljától függ.

Fő keresési módszerek:

1. Mélységi keresés (DFS - Depth-First Search): Egy ágon megy a lehető legmélyebbre, mielőtt a szomszédos ágra lépne. Verem (stack) használatával valósítható meg (nyílt vagy rekurzióval).

   • Előzetes bejárás (Pre-order): Látogassa meg a gyökeret, majd a bal alárendet, majd a jobb alárendet.
   • In-order bejárás: Látogassa meg a bal alárendet, majd a gyökeret, majd a jobb alárendet. Ez a bináris keresőfáknál használatos, hogy rendezett listát kapjunk.
   • Post-order: Látogassa meg a bal alárendet, majd a jobb alárendet, majd a gyökeret.

2. Szélességi keresés (BFS - Breadth-First Search): Minden szomszédot vizsgál egy szinten, mielőtt a következő szintre lépne. Sor (queue) használatával valósítható meg.

Példa DFS (In-order) bináris fára:

// TreeNode a bináris fa csomópontját jelöli
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal végrehajtja az in-order bejárást
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Rekurzív hívás a bal alárendre
	result = append(result, InOrderTraversal(root.Left)...)
	// A jelenlegi csomópont meglátogatása
	result = append(result, root.Val)
	// Rekurzív hívás a jobb alárendre
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

BFS példa:

// TreeNode a bináris fa csomópontját jelöli
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal végrehajtja a BFS bejárást
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Sor a csomópontok tárolására a jelenlegi szinten
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// Első elem kivétele a sorból
		node := queue[0]
		queue = queue[1:]

		// Az érték hozzáadása az eredményhez
		result = append(result, node.Val)

		// Bal gyermek hozzáadása, ha létezik
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// Jobb gyermek hozzáadása, ha létezik
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

Bináris keresőfák (BST) esetén, ahol a bal alárendelt kisebb, mint a gyökér, a jobb pedig nagyobb:

3. Bináris keresés: A konkrét érték keresésekor összehasonlítjuk a gyökérrel. Ha kisebb, a bal alárendeltben keresünk; ha nagyobb, a jobb alárendeltben. Ez a leghatékonyabb keresési stratégia a BST-ben.

// TreeNode a bináris keresőfa csomópontját jelöli
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST végzi a bináris keresést a BST-ben
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // A csomópont megtalálva vagy az fa üres
	}

	if target < root.Val {
		// A bal alárendeltben keres
		return SearchBST(root.Left, target)
	}
	// A jobb alárendeltben keres
	return SearchBST(root.Right, target)
}

A keresési algoritmus kiválasztása a feladattól és a fa jellemzőitől függ. A DFS alkalmas arra, hogy mélyen végigmenjen egy ágon vagy útvonalat találjon a célhoz. A BFS a legrövidebb út megtalálására vagy szintenkénti bejárásra alkalmas. A bináris keresés hatékony a rendezett struktúrákban, mint például a BST.