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