Какова сложность поиска элемента в сбалансированном двоичном дереве?

Сложность поиска элемента в сбалансированном двоичном дереве (например, АВЛ-дереве или красно-чёрном дереве) составляет O(log n), где n — количество узлов в дереве.

Это достигается за счёт того, что на каждом шаге сравнения алгоритм отбрасывает примерно половину оставшихся узлов, значительно сужая область поиска. Сбалансированность гарантирует, что высота дерева не будет значительно превышать log n.

Пример реализации поиска в двоичном дереве на Go:
(Этот код демонстрирует сам механизм поиска, который одинаков как для сбалансированных, так и для несбалансированных деревьев).

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

// Search ищет значение в дереве, начиная с корня root.
func Search(root *Node, value int) bool {
    // Базовый случай: дошли до конца ветки, узел не найден.
    if root == nil {
        return false
    }

    // Узел найден.
    if root.Value == value {
        return true
    }

    // Если искомое значение меньше текущего, идём в левое поддерево.
    if value < root.Value {
        return Search(root.Left, value)
    }

    // Иначе идём в правое поддерево.
    return Search(root.Right, value)
}

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