როგორ მუშაობს ხის ძებნა?

ძებნა ხეებში დამოკიდებულია მათ სტრუქტურაზე და ძებნის მიზანზე.

ძებნის ძირითადი მეთოდები:

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.