Почему поиск в дереве происходит за логарифмическое время

Поиск в сбалансированном дереве (например, 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)

Нюансы:

1. Дерево должно быть сбалансированным — иначе вырождается в O(n) для вырожденного случая (цепочки узлов)
2. Логарифмическая сложность достигается только при равномерном распределении элементов
3. Основание логарифма зависит от степени ветвления (для бинарного log₂n)