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

Поиск в сбалансированном бинарном дереве поиска (например, AVL или красно-чёрном) имеет среднюю и худшую временную сложность O(log n), где n — количество узлов.

Почему O(log n)? Сбалансированность гарантирует, что высота дерева пропорциональна логарифму числа элементов. Каждый шаг поиска делит пространство поиска примерно пополам.

Пример на C#:

public class BinarySearchTree
{
    public class Node
    {
        public int Key;
        public Node Left, Right;
        public Node(int item) => Key = item;
    }

    // Рекурсивный поиск
    public Node Search(Node root, int key)
    {
        // Базовый случай: узел не найден или найден
        if (root == null || root.Key == key)
            return root;

        // Ключ меньше корня -> ищем в левом поддереве
        if (key < root.Key)
            return Search(root.Left, key);
        // Иначе ищем в правом
        return Search(root.Right, key);
    }
}

Контраст с несбалансированным деревом: В вырожденном случае (например, когда узлы добавляются по порядку) дерево превращается в связный список, и сложность поиска деградирует до O(n). Сбалансированные деревья (AVL, красно-чёрные) автоматически перестраиваются при вставке/удалении, чтобы избежать этого.