Как работает поиск по Бинарному дереву

1️⃣ Как кратко ответить

Поиск в бинарном дереве выполняется рекурсивно или итеративно, начиная с корня. Сравниваем искомое значение с текущим узлом: если меньше — переходим в левое поддерево, если больше — в правое. Процесс повторяется, пока не найдено значение или не достигнут лист дерева.

2️⃣ Подробное объяснение темы

Бинарное дерево — это структура данных, в которой каждый узел имеет не более двух потомков, называемых левым и правым. Бинарное дерево поиска (BST) — это особый вид бинарного дерева, где для каждого узла выполняется следующее условие: все значения в левом поддереве меньше значения в узле, а все значения в правом поддереве больше.

Поиск в бинарном дереве поиска (BST) — это процесс нахождения узла, содержащего определенное значение. Этот процесс эффективен благодаря свойствам BST, которые позволяют сократить количество проверяемых узлов.

Пример кода поиска в бинарном дереве

package main
​
import "fmt"
​
// Node представляет узел бинарного дерева
type Node struct {
    value int
    left  *Node
    right *Node
}
​
// searchBST выполняет поиск значения в бинарном дереве поиска
func searchBST(root *Node, target int) *Node {
    // Если текущий узел пустой, значит значение не найдено
    if root == nil {
        return nil
    }
​
    // Если значение текущего узла равно искомому, возвращаем узел
    if root.value == target {
        return root
    }
​
    // Если искомое значение меньше текущего, ищем в левом поддереве
    if target < root.value {
        return searchBST(root.left, target)
    }
​
    // Если искомое значение больше текущего, ищем в правом поддереве
    return searchBST(root.right, target)
}
​
func main() {
    // Создаем простое бинарное дерево поиска
    root := &Node{value: 10}
    root.left = &Node{value: 5}
    root.right = &Node{value: 15}
    root.left.left = &Node{value: 3}
    root.left.right = &Node{value: 7}
    root.right.right = &Node{value: 18}
​
    // Ищем значение 7 в дереве
    result := searchBST(root, 7)
​
    if result != nil {
        fmt.Printf("Значение %d найдено в дереве.\n", result.value)
    } else {
        fmt.Println("Значение не найдено в дереве.")
    }
}

Объяснение кода

1. Структура Node: Определяет узел бинарного дерева с полями value, left и right, которые представляют значение узла и ссылки на левого и правого потомков соответственно.

2. Функция searchBST: Выполняет рекурсивный поиск в бинарном дереве.

   • Если текущий узел nil, значит, мы достигли конца пути, и значение не найдено.
   • Если значение текущего узла равно искомому, возвращаем текущий узел.
   • Если искомое значение меньше текущего, рекурсивно ищем в левом поддереве.
   • Если искомое значение больше текущего, рекурсивно ищем в правом поддереве.

3. Функция main: Создает пример бинарного дерева поиска и выполняет поиск значения 7. Если значение найдено, выводится сообщение с найденным значением, иначе — сообщение о том, что значение не найдено.

Поиск в бинарном дереве поиска эффективен, так как в среднем имеет временную сложность O(log n), где n — количество узлов в дереве. Это достигается за счет того, что на каждом шаге поиска мы отбрасываем половину оставшихся узлов.