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

Сложность поиска в базовом бинарном дереве поиска (Binary Search Tree, BST) составляет O(h), где h — высота дерева. Логарифмическая сложность O(log n) гарантируется только для сбалансированных деревьев (как в std::map, реализованном красно-черным деревом).

Сложность деградирует до линейной O(n) в случае вырождения дерева в связный список. Это происходит при:

1. Последовательной вставке отсортированных (или почти отсортированных) данных. Базовый алгоритм вставки BST помещает большие значения в правого ребенка, что при отсортированной последовательности создает "вертикальную" структуру.

   // Вырожденное дерево после вставки 1, 2, 3, 4, 5
   //    1
   //     
   //      2
   //       
   //        3
   //         
   //          4
   //           
   //            5
   // Поиск числа 5 потребует 5 сравнений (O(n)).

2. Использовании BST без механизмов самобалансировки (например, наивная реализация для обучения).

Решение: Использование сбалансированных деревьев поиска, которые автоматически поддерживают высоту ~O(log n):

• AVL-деревья: Строгая балансировка, быстрый поиск.
• Красно-черные деревья (используются в std::map, std::set): Менее строгая балансировка, но меньше операций поворота при модификациях.
• B-деревья, Splay-деревья и др.

В C++ контейнеры std::set и std::map гарантируют логарифмическую сложность операций, так как реализованы как красно-черные деревья.