Какова временная сложность операций вставки, поиска и удаления в бинарном дереве в среднем и худшем случае?

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

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

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

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

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

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

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

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

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

cpp