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

Сложность поиска в бинарном дереве поиска (BST) будет не логарифмической в следующих случаях:

1. Несбалансированное бинарное дерево (вырождение в список)

Когда дерево становится несбалансированным, оно может вырождаться в односвязный список. В худшем случае все элементы находятся только в правом (или только в левом) поддереве:

// Вырожденное дерево O(n)
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

// Пример вырождения: вставляем уже отсортированный массив
TreeNode* root = nullptr;
for (int x : {1, 2, 3, 4, 5}) {
    // Вставляем - получаем цепочку (right, right, right, ...)
}
// Поиск любого элемента требует O(n) операций

Это происходит когда:

• Элементы вставляются в отсортированном порядке (возрастающем или убывающем)
• Нет балансировки после вставок

2. Не является деревом поиска

Если нарушено BST свойство (left < parent < right), то мы не можем использовать метод деления пополам. Поиск становится линейным O(n):

// Неправильное дерево - не BST свойство
struct BadTree {
    TreeNode* root;
    // root->val = 5, root->left->val = 10, root->right->val = 3
    // Это нарушает BST свойство!
};

3. Поиск в обычном бинарном дереве (не BST)

Обычное бинарное дерево без свойства BST требует полного обхода - O(n):

// Обход всего дерева для поиска элемента
void findInBinaryTree(TreeNode* root, int target) {
    if (!root) return nullptr;
    if (root->val == target) return root;
    
    // Нельзя оптимизировать - ищем везде
    TreeNode* left = findInBinaryTree(root->left, target);
    if (left) return left;
    return findInBinaryTree(root->right, target);
}

4. Поиск вторичного ключа в BST

Если индексируем дерево по первичному ключу (обеспечивает O(log n)), но ищем по вторичному ключу, сложность становится O(n):

// BST по id, но ищем по name
struct User {
    int id;      // primary key - дерево отсортировано по этому
    string name; // вторичный ключ
};

// Поиск по name требует обхода всего дерева
User* findByName(TreeNode* root, const string& name) {
    if (!root) return nullptr;
    if (root->val.name == name) return root;
    
    User* left = findByName(root->left, name);
    if (left) return left;
    return findByName(root->right, name);
}

Решения

Для гарантированной логарифмической сложности:

• AVL дерево - высота всегда сбалансирована (разница <= 1)
• Red-Black дерево - вероятностная балансировка, быстрее на вставку-удаление
• B-дерево - для больших данных, оптимизирует дисковый доступ
• Хеш-таблицы - O(1) в среднем случае для точного поиска

// Гарантированная O(log n) с AVL
AVL<int> avl;
for (int x : {5, 3, 7, 1, 9, 2, 4}) {
    avl.insert(x); // автоматическая балансировка
}
// Поиск - всегда O(log n)

Ключевое правило: O(log n) поиск возможен только если дерево сбалансировано и удовлетворяет BST свойству.