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

Сложность поиска в бинарном дереве поиска (Binary Search Tree, BST) зависит от его сбалансированности:

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

Пример рекурсивного поиска в BST на Swift:

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) { self.val = val }
}

func search(in root: TreeNode?, value: Int) -> Bool {
    // Базовый случай: узел пуст или значение найдено
    guard let node = root else { return false }
    if node.val == value { return true }

    // Рекурсивный случай: идем в левое или правое поддерево
    if value < node.val {
        return search(in: node.left, value: value)
    } else {
        return search(in: node.right, value: value)
    }
}

// Использование
let root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
print(search(in: root, value: 5)) // true
print(search(in: root, value: 12)) // false

Для гарантированной производительности O(log n) используются самобалансирующиеся деревья (AVL, Красно-черные).