Почему поиск в сбалансированном бинарном дереве выполняется за O(log N)?

Поиск в сбалансированном бинарном дереве (например, AVL, красно-черном дереве) выполняется за логарифмическое время O(log N), где N — количество узлов. Это обусловлено двумя ключевыми факторами:

1. Свойство бинарного дерева поиска (BST): Для каждого узла все значения в его левом поддереве меньше значения узла, а в правом — больше. Это позволяет на каждом шаге отсекать половину оставшихся элементов.
2. Сбалансированность: Высота сбалансированного дерева гарантированно составляет O(log N). Это предотвращает вырождение дерева в связный список, где поиск занял бы O(N) времени.

Пример алгоритма поиска в 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), и поиск деградирует до O(N).
• Основание логарифма: Для бинарных деревьев используется логарифм по основанию 2 (log₂N), так как на каждом шаге мы выбираем одно из двух поддеревьев. Для деревьев с большей степенью ветвления основание логарифма будет другим.