Quelle est la complexité temporelle des opérations d'insertion, de recherche et de suppression dans un arbre binaire en moyenne et en pire cas?

Временная сложность операций вставки, поиска и удаления в бинарном дереве

Сложность указанных операций зависит от высоты дерева.

В среднем случае

В хорошо сбалансированном бинарном дереве высота примерно равна $log_2(n)$, где $n$ - количество узлов.

Таблица временной сложности в среднем случае:

Операция	Временная сложность
Вставка	$O(log_2(n))$
Поиск	$O(log_2(n))$
Удаление	$O(log_2(n))$

В худшем случае

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

Таблица временной сложности в худшем случае:

Операция	Временная сложность
Вставка	$O(n)$
Поиск	$O(n)$
Удаление	$O(n)$

Пример вырожденного дерева (дерево из одного "ребра" на каждом уровне):

// Пример вырожденного бинарного дерева
// Каждый узел имеет только одного потомка

struct Node {
    int key;
    Node* left;
    Node* right;

    Node(int k) : key(k), left(nullptr), right(nullptr) {}
};

// Вставка элементов в порядке возрастания приведет к вырожденному дереву
void insert(Node*& root, int key) {
    if (!root) {
        root = new Node(key);
        return;
    }
    if (key < root->key) {
        insert(root->left, key);
    } else {
        insert(root->right, key);
    }
}

int main() {
    Node* root = nullptr;
    insert(root, 1);
    insert(root, 2);
    insert(root, 3);
    // ... и так далее
    // Это создаст вырожденное дерево
    return 0;
}