Kaip veikia medžio paieška?

Paieška medyje priklauso nuo jo struktūros ir paieškos tikslo.

Pagrindiniai paieškos būdai:

Giliausios paieškos (DFS - Depth-First Search): eina maksimaliai giliai viename šake, prieš pereidamas prie šalia esančio. Įgyvendinama naudojant steką (tiesiogiai arba rekursijos būdu).
- Išankstinė apžvalga (Pre-order): aplankyti šaknį, tada kairįjį medį, tada dešinįjį medį.
- In-order apžvalga (In-order): aplankyti kairįjį medį, tada šaknį, tada dešinįjį medį. Naudojama rikiuotų paieškos medžių elementų sąrašui gauti.
- Post-order apžvalga (Post-order): aplankyti kairįjį medį, tada dešinįjį, tada šaknį.
Plotinės paieškos (BFS - Breadth-First Search): tiria visus kaimynus esamo mazgo tame pačiame lygyje, prieš pereidamas į kitą lygį. Įgyvendinama naudojant eilę.

Pavyzdys DFS (In-order) dvejetainiam medžiui:

// TreeNode reprezentuoja dvejetainio medžio mazgą
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal atlieka inorder apžvalgą
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Rekursinis kvietimas kairiam medžiui
	result = append(result, InOrderTraversal(root.Left)...)
	// Aplankyti dabartinį mazgą
	result = append(result, root.Val)
	// Rekursinis kvietimas dešiniam medžiui
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

Pavyzdys BFS:

// TreeNode reprezentuoja dvejetainio medžio mazgą
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal atlieka BFS apžvalgą
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// eilė, sauganti dabartinio lygio mazgus
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// išimti pirmą elementą iš eilės
		node := queue[0]
		queue = queue[1:]

		// pridėti mazgo reikšmę į rezultatą
		result = append(result, node.Val)

		// pridėti kairįjį vaiką į eilę, jei jis yra
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// pridėti dešinįjį vaiką į eilę, jei jis yra
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

Dvejetainiams paieškos medžiams (BST), kur kairysis medis yra mažesnis už šaknį, o dešinysis - didesnis:

Dvejetainė paieška: ieškant konkrečios reikšmės, ją lyginame su šaknimi. Jei reikšmė mažesnė, ieškome kairiajame medyje; jei didesnė, dešiniajame. Tai yra efektyviausia strategija BST.

// TreeNode reprezentuoja dvejetainio paieškos medžio mazgą
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST atlieka dvejetainę paiešką BST
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // mazgas rastas arba medis tuščias
	}

	if target < root.Val {
		// ieškoti kairiajame medyje
		return SearchBST(root.Left, target)
	}
	// ieškoti dešiniajame medyje
	return SearchBST(root.Right, target)
}

Paieškos algoritmo pasirinkimas priklauso nuo užduoties ir medžio savybių. DFS tinka, kai reikia gilintis į vieną šaką arba rasti kelią iki tikslo. BFS tinka trumpiausio kelio paieškai arba sluoksnių apžvalgai. Dvejetainė paieška efektyvi ieškant konkrečios reikšmės rūšiuotuose duomenų struktūrose, tokiuose kaip BST.