Ինչպես է աշխատում ծառի որոնումը?

Որոնումը ծառի մեջ կախված է նրա կառուցվածքից և որոնման նպատակից:

Հիմնական որոնման մեթոդները՝

1. Ավելի խորքային որոնում (DFS - Depth-First Search): Գնացեք առավելագույնը խորությամբ մեկ ճյուղում, նախքան անցնել հարևանին: Իրականացվում է ստեկի (բացահայտ կամ ռեկուրսիվ) օգտագործմամբ:

   • Նախնական շրջայց (Pre-order): Այցելել տերևը, ապա ձախ ենթաարևը, ապա աջ ենթաարևը:
   • In-order: Այցելել ձախ ենթաարևը, ապա տերևը, ապա աջ ենթաարևը: Օգտագործվում է բինար որոնողական ծառերում՝ ստանալով դասավորված ցուցակ:
   • Post-order: Այցելել ձախ ենթաարևը, ապա աջ ենթաարևը, ապա տերևը:

2. Լայնության որոնում (BFS - Breadth-First Search): Ուսումնասիրել բոլոր հարևաններին նույն մակարդակում, նախքան անցնել հաջորդ մակարդակ:

Նմուշ DFS (In-order) բինար ծառի համար:

// TreeNode ներկայացնում է բինար ծառի հանգույցը
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal իրականացնում է inorder շրջայց
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Ռեկուրսիվ կանչ ձախ ենթաարևի համար
	result = append(result, InOrderTraversal(root.Left)...)
	// Այցելել ընթացիկ հանգույցը
	result = append(result, root.Val)
	// Ռեկուրսիվ կանչ աջ ենթաարևի համար
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

BFS օրինակ:

// TreeNode ներկայացնում է բինար ծառի հանգույցը
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal իրականացնում է BFS շրջայց
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Քարտեզ՝ պահելու հանգույցները ընթացիկ մակարդակում
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// Առաջին տարրից հանելը
		node := queue[0]
		queue = queue[1:]

		// Հանգույցի արժեքը ավելացնել արդյունք
		result = append(result, node.Val)

		// Լավ երեխային ավելացնել, եթե կա
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// Աջ երեխային ավելացնել, եթե կա
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

Բինար որոնողական ծառերի համար (BST), որտեղ ձախ ենթաարևը փոքր է, քան արմատը, իսկ աջը՝ մեծ:

3. Բինար որոնում: Որոնելով կոնկրետ արժեք, համեմատում ենք այն արմատի հետ: Եթե փոքր է, որոնում ենք ձախ ենթաարևում; եթե մեծ է,՝ աջում: Սա ամենաարդյունավետ ռազմավարությունն է BST-ում:

// TreeNode ներկայացնում է բինար որոնողական ծառի հանգույցը
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST իրականացնում է բինար որոնում BST-ում
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // Հանգույցը գտնվել է կամ ծառը դատարկ է
	}

	if target < root.Val {
		// Փնտրում ենք ձախ ենթաարևում
		return SearchBST(root.Left, target)
	}
	// Փնտրում ենք աջ ենթաարևում
	return SearchBST(root.Right, target)
}

Ընտրությունը որոնման ալգորիթմի՝ կախված է խնդրից և ծառի բնութագրերից: DFS-ը հարմար է այն դեպքերում, երբ անհրաժեշտ է խորանալ մի ճյուղում կամ գտնել ճանապարհ դեպի նպատակակետը: BFS-ը հարմար է ամենափոքր ճանապարհը գտնելու կամ մակարդակով շրջելու համար: Բինար որոնումը արդյունավետ է սորտավորված կառուցվածքներում, ինչպիսիք են BST-ը։