Наихудший случай временной сложности вставки в бинарное дерево может возникнуть в следующих случаях:

• Вырожденное дерево. 4 Это дерево, в котором элементы попадали при добавлении в позицию крайнего левого узла (наименьшие число) или крайнего большего узла (наибольшие). 4 Например, если всё левое дерево пусто на каждом уровне, есть только правые деревья, и в таком случае дерево вырождается в список. 4 В этом случае все операции по данной структуре приближаются ко временной сложности O(N). 4
• Вставка всех ключей упорядоченным образом. 1 Например, если вставлять числа 1, 2, 3, …, n таким образом, чтобы на каждом шаге вставлялось либо наименьшее, либо наибольшее из оставшихся чисел. 1

Если используется самобалансирующееся бинарное дерево поиска, наихудшее время выполнения вставки — Θ(log n). 1 Это связано с тем, что такие деревья гарантируют, что высота дерева никогда не превышает Θ(log n), а время выполнения вставки в наихудшем случае пропорционально высоте дерева. 1