В сбалансированном бинарном дереве поиска (например, AVL или красно-черном) высота дерева поддерживается логарифмической относительно количества элементов (O(log n)). Однако, если говорить о хеш-таблицах (dict в Python), то поиск в среднем занимает O(1), так как ключ хешируется и доступ происходит напрямую к нужному "ведру". Пример с хеш-таблицей: ``` d = {'a': 1, 'b': 2} print(d['a']) # O(1) в среднем случае ``` **Нюансы:** - В худшем случае (коллизии) поиск в хеш-таблице может деградировать до O(n). - В Python `dict` реализован как хеш-таблица с открытой адресацией, что обеспечивает высокую эффективность. - Деревья (например, `SortedDict` из `sortedcontainers`) дают O(log n), но сохраняют порядок.