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

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

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

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

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

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

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

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

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

При