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

Нет, не всегда. Сложность поиска в бинарном дереве зависит от его высоты.

• В сбалансированном бинарном дереве (например, AVL-дереве или красно-черном дереве) высота пропорциональна log(n), где n - количество узлов. В этом случае сложность поиска логарифмическая, O(log n).

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

Таким образом, логарифмическая сложность гарантируется для сбалансированных бинарных деревьев.