Kā darbojas meža meklēšana?

Meža meklēšana ir atkarīga no tā struktūras un meklēšanas mērķa.

Galvenie meklēšanas veidi:

Dziļuma meklēšana (DFS - Depth-First Search): dodas maksimāli dziļi vienā zarā, pirms pāriet uz blakus esošo. Realizē ar steku (tieši vai rekursijas veidā).
- Priekšējā apmeklējuma (Pre-order): apmeklēt sakni, tad kreiso koku, tad labo koku.
- In-order apmeklējums (In-order): apmeklēt kreiso koku, tad sakni, tad labo koku. Izmanto, lai iegūtu sakārtotu elementu sarakstu no binārajiem mežiem.
- Pēcapmeklējums (Post-order): apmeklēt kreiso koku, tad labo koku, tad sakni.
Plašuma meklēšana (BFS - Breadth-First Search): izpēta visus kaimiņus esošajā mezglā vienā līmenī, pirms pāriet uz nākamo līmeni. Realizē ar rindu.

Piemērs DFS (In-order) bināram kokam:

// TreeNode pārstāv bināro koku mezglu
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal veic in-order apmeklējumu
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Rekursīvs izsaukums kreisajam kokam
	result = append(result, InOrderTraversal(root.Left)...)
	// Apmeklēt pašreizējo mezglu
	result = append(result, root.Val)
	// Rekursīvs izsaukums labajam kokam
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

Piemērs BFS:

// TreeNode pārstāv bināro koku mezglu
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal veic BFS apmeklējumu
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// rinda, kas satur mezglus pašreizējā līmenī
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// izņem pirmo elementu no rindas
		node := queue[0]
		queue = queue[1:]

		// pievieno mezgla vērtību rezultātam
		result = append(result, node.Val)

		// ja ir kreisais bērns, pievieno to rindai
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// ja ir labais bērns, pievieno to rindai
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

Bināro mežu (BST), kur kreisais mazāks par sakni, bet labais lielāks:

Binārā meklēšana: meklējot konkrētu vērtību, salīdzina to ar sakni. Ja vērtība ir mazāka, meklē kreisajā zarā; ja lielāka, labajā. Šī ir efektīvākā meklēšanas stratēģija BST.

// TreeNode pārstāv bināro meklēšanas koku
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST veic bināro meklēšanu BST
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // mezgls atrasts vai koks tukšs
	}

	if target < root.Val {
		// meklēt kreisajā zarā
		return SearchBST(root.Left, target)
	}
	// meklēt labajā zarā
	return SearchBST(root.Right, target)
}

Meklēšanas algoritma izvēle ir atkarīga no uzdevuma un koka īpašībām. DFS ir piemērots, ja nepieciešams dziļi izpētīt vienu zarojumu vai atrast ceļu līdz mērķim. BFS ir piemērots īsākā ceļa meklēšanai vai līmeņu pārskatīšanai. Binārā meklēšana ir efektīva, meklējot konkrētu vērtību sakārtotās struktūrās, piemēram, BST.