Kuidas töötab puu otsing?

Otsing tree'is sõltub selle struktuurist ja otsingu eesmärgist.

Peamised otsingusüüdemed:

1. Sügavusotsing (DFS - Depth-First Search): liigub maksimaalselt sügavale ühe haru, enne kui liigub teise juurde. Rakendatakse virna (otseselt või rekursiooni kaudu).

   • Eelkäigu läbimine (Pre-order): külastada juuri, siis vasakut puud, siis paremat puud.
   • In-order läbimine (In-order): külastada vasakut puud, siis juuri, siis paremat puud. Kasutatakse sorteeritud elementide nimekirja saamiseks binaarsetest otsingupuu struktuuridest.
   • Pärastläbimine (Post-order): külastada vasakut puud, siis paremat puud, siis juuri.

2. Laiusotsing (BFS - Breadth-First Search): uurib kõiki naabreid samal tasemel enne järgmisele tasemele liikumist. Rakendatakse järjekorra abil.

Näide DFS (In-order) binaarpuu jaoks:

// TreeNode esindab binaarpuu sõlme
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal teostab inorder läbimise
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Rekursiivne kõne vasakule alampuule
	result = append(result, InOrderTraversal(root.Left)...)
	// Külasta praegune sõlm
	result = append(result, root.Val)
	// Rekursiivne kõne paremale alampuule
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

Näide BFS:

// TreeNode esindab binaarpuu sõlme
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal teostab BFS läbimise
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// järjekord, mis hoiab taseme sõlmi
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// esimese elemendi eemaldamine järjekorrast
		node := queue[0]
		queue = queue[1:]

		// sõlme väärtuse lisamine tulemusele
		result = append(result, node.Val)

		// vasak lapse lisamine järjekorda, kui see eksisteerib
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// parema lapse lisamine järjekorda, kui see eksisteerib
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

Binara otsingupuu (BST), kus vasak alam on väiksem juurest ja parem suurem:

3. Binārā meklēšana: meklides konkreetset väärtust, võrdleme seda juurega. Kui väärtus on väiksem, otsime vasakult; kui suurem, paremal. See on kõige tõhusam otsingustrateegia BST-s.

// TreeNode esindab binaarset otsingupuu sõlme
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST teostab binaarset otsingut BST-s
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // sõlm leitud või puu on tühi
	}

	if target < root.Val {
		// otsing vasakult
		return SearchBST(root.Left, target)
	}
	// otsing paremal
	return SearchBST(root.Right, target)
}

Otsingualgoritmi valik sõltub ülesandest ja puu omadustest. DFS sobib, kui vaja on sügavalt läbi minna või leida tee sihile. BFS sobib lühima tee otsimiseks või tasemete läbivaatuseks. Binārset otsingut on tõhus, kui otsitav väärtus on sorteeritud struktuurides, nagu BST.