Kako funkcioniše pretraga u stablu?

Проналажење у дрвету зависи од његове структуре и циља претраге.

Главни начини претраге:

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.