Как работает поиск в дереве?

Поиск в дереве зависит от его структуры и цели поиска.

Основные способы поиска:

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.