Поиск в сбалансированном дереве (например, AVL или красно-черном) происходит за O(log n), потому что на каждом шаге алгоритм отсекает половину оставшихся элементов. Это возможно благодаря свойству бинарного дерева поиска (BST), где для каждого узла: левое поддерево содержит меньшие значения, правое — большие. Пример для BST: ``` def search(root, key): if root is None or root.val == key: return root if root.val < key: return search(root.right, key) return search(root.left, key) ``` Нюансы: - Дерево должно быть сбалансированным — иначе вырождается в O(n) для вырожденного случая (цепочки узлов) - Логарифмическая сложность достигается только при равномерном распределении элементов - Основание логарифма зависит от степени ветвления (для бинарного log₂n)