Как работает поиск в бинарном дереве поиска (Binary Search Tree)?

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

Алгоритм поиска:

1. Начать с корневого узла.
2. Сравнить искомое значение с ключом текущего узла.
3. Если значения совпадают — узел найден.
4. Если искомое значение меньше — перейти к левому дочернему узлу и повторить шаг 2.
5. Если искомое значение больше — перейти к правому дочернему узлу и повторить шаг 2.
6. Если дочерний узел, к которому нужно перейти, отсутствует (nil), значит, искомого значения в дереве нет.

Реализация на Go (рекурсивный и итеративный подходы):

package main

type Node struct {
    Value int
    Left  *Node
    Right *Node
}

// Рекурсивный поиск
func SearchRecursive(node *Node, target int) *Node {
    if node == nil || node.Value == target {
        return node
    }

    if target < node.Value {
        return SearchRecursive(node.Left, target)
    }

    return SearchRecursive(node.Right, target)
}

// Итеративный поиск (более эффективен по памяти)
func SearchIterative(root *Node, target int) *Node {
    current := root
    for current != nil {
        if target == current.Value {
            return current
        }
        if target < current.Value {
            current = current.Left
        } else {
            current = current.Right
        }
    }
    return nil
}

Сложность алгоритма:

• В среднем/лучшем случае: O(log n) — для сбалансированного дерева, так как на каждом шаге мы отсекаем половину оставшихся узлов.
• В худшем случае: O(n) — для несбалансированного (вырожденного) дерева, которое превращается в связный список.