Ağacda axtarış necə işləyir?

Axtarış ağacında onun quruluşu və axtarış məqsədindən asılıdır.

Əsas axtarış üsulları:

Dərinlikdə axtarış (DFS - Depth-First Search): Bir budaqda ən dərinə qədər gedir, sonra qonşu budağa keçir. Yığım (stack) istifadə edilərək həyata keçirilir (açıq və ya qapalı şəkildə rekursiya ilə).
- Əvvəlcədən keçid (Pre-order): Kökü ziyarət et, sonra sol alt ağacı, sonra sağ alt ağacı.
- İn-order keçid: Sol alt ağacı ziyarət et, sonra kökü, sonra sağ alt ağacı. Bu, sıralanmış elementlər siyahısı əldə etmək üçün ikili axtarış ağaclarında istifadə olunur.
- Post-order: Sol alt ağacı, sonra sağ alt ağacı, sonra kökü.
Enində axtarış (BFS - Breadth-First Search): Eyni səviyyədəki bütün qonşuları araşdırır, sonra növbəti səviyyəyə keçir. Növbə istifadə edilərək həyata keçirilir.

İkili axtarış ağacı üçün DFS (İn-order) nümunəsi:

// TreeNode ikili ağacın düyünü təmsil edir
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal inorder keçidini həyata keçirir
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Sol alt ağac üçün rekursiv çağırış
	result = append(result, InOrderTraversal(root.Left)...)
	// Cari düyünü ziyarət et
	result = append(result, root.Val)
	// Sağ alt ağac üçün rekursiv çağırış
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

BFS nümunəsi:

// TreeNode ikili ağacın düyünü təmsil edir
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal BFS keçidini həyata keçirir
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Cari səviyyədəki düyünləri saxlamaq üçün növbə
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// İlk elementi çıxarırıq
		node := queue[0]
		queue = queue[1:]

		// Düyünün dəyərini nəticəyə əlavə et
		result = append(result, node.Val)

		// Sol övladını əlavə et, varsa
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// Sağ övladını əlavə et, varsa
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

BST üçün, yəni sol alt ağac kökdən kiçik, sağ alt ağac isə böyükdür:

İkili axtarış: Müəyyən bir dəyəri axtararkən, onu kök ilə müqayisə edirik. Əgər dəyər kiçikdirsə, sol alt ağacda axtarırıq; əks halda, sağ alt ağacda. Bu, ən effektiv axtarış strategiyasıdır.

// TreeNode ikili axtarış ağacının düyünü təmsil edir
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST BST-də ikili axtarış edir
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // Düyün tapıldı və ya ağac boşdur
	}

	if target < root.Val {
		// Sol alt ağacda axtarırıq
		return SearchBST(root.Left, target)
	}
	// Sağ alt ağacda axtarırıq
	return SearchBST(root.Right, target)
}

Axtarış alqoritminin seçimi və ağacın xüsusiyyətlərindən asılıdır. DFS bir budaqda dərinə getmək və ya məqsədə çatmaq üçün istifadə olunur. BFS ən qısa yolu tapmaq və ya səviyyə-səviyyə keçid üçün uyğundur. İkili axtarış isə sıralanmış strukturlarda, məsələn, BST-də, konkret dəyəri tapmaq üçün effektivdir.