Daraxtda qidiruv qanday ishlaydi?

Bir daraxtdagi qidiruv uning tuzilishi va qidiruv maqsadiga bog'liq.

Asosiy qidiruv usullari:

1. Chuqurlik bo'yicha qidiruv (DFS - Depth-First Search): Bir shox ichida maksimal darajaga boradi, keyin keyingi shoxga o'tadi. Stack (to'g'ridan-to'g'ri yoki rekurziya orqali) yordamida amalga oshiriladi.

   • Oldindan yurish (Pre-order): ildizni tashrif buyurish, so'ng chap bo'linma, keyin o'ng bo'linma.
   • In-order yurish: chap bo'linmani tashrif buyurish, so'ng ildiz, keyin o'ng bo'linma. Bu ikkilamchi qidiruv daraxtlarida tartiblangan elementlar ro'yxatini olish uchun ishlatiladi.
   • Post-order yurish: chap bo'linma, o'ng bo'linma, ildiz.

2. Kenglik bo'yicha qidiruv (BFS - Breadth-First Search): Har bir darajadagi barcha qo'shnilarni tekshiradi, keyin keyingi darajaga o'tadi. Queue yordamida amalga oshiriladi.

DFS (In-order) uchun misol:

// TreeNode ikkilamchi daraxt tugunini ifodalaydi
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal inorder yurishni amalga oshiradi
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Chap bo'linma uchun rekursiv chaqiriq
	result = append(result, InOrderTraversal(root.Left)...)
	// Hozirgi tugunni tashrif buyurish
	result = append(result, root.Val)
	// O'ng bo'linma uchun rekursiv chaqiriq
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

BFS uchun misol:

// TreeNode ikkilamchi daraxt tugunini ifodalaydi
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal BFS yurishni amalga oshiradi
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Joriy darajadagi tugunlarni saqlash uchun queue
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// Queue ning birinchi elementini chiqarish
		node := queue[0]
		queue = queue[1:]

		// Tugunning qiymatini natijaga qo'shish
		result = append(result, node.Val)

		// Chap farzandni queue ga qo'shish, agar mavjud bo'lsa
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// O'ng farzandni queue ga qo'shish, agar mavjud bo'lsa
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

Ikkiyilama qidiruv daraxtlari (BST), chap bo'linma kichik, o'ng katta:

3. Ikkiyilama qidiruv: Aniq qiymatni qidirishda, uni ildiz bilan solishtiramiz. Agar kichik bo'lsa, chap bo'linmada qidiramiz; agar katta bo'lsa, o'ngda. Bu BSTda eng samarali qidiruv strategiyasidir.

// TreeNode ikkilamchi qidiruv daraxtini ifodalaydi
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST BSTda ikkiyilama qidiruv
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // Tugun topildi yoki daraxt bo'sh
	}

	if target < root.Val {
		// Chap bo'linmada qidirish
		return SearchBST(root.Left, target)
	}
	// O'ng bo'linmada qidirish
	return SearchBST(root.Right, target)
}

Qidiruv algoritmining tanlovi vazifa va daraxtning xususiyatlariga bog'liq. DFS, bir shoxni chuqurroq o'rganish yoki maqsadga yo'l topish uchun mos. BFS, eng qisqa yo'lni topish yoki darajalarga bo'lib o'tish uchun. Ikkiyilama qidiruv, tartiblangan tuzilmalar, masalan, BSTda, aniq qiymatni topish uchun samarali.