Знакомы ли вы с деревьями поиска, какая у них сложность поиска

Что проверяют

Понимаете ли вы, откуда берётся логарифм и когда он превращается в линию. Следом обычно спрашивают, почему в базах данных используют B-деревья, а не красно-чёрные, и что из этого есть в стандартной библиотеке Go.

Как отвечать

Бинарное дерево поиска держит инвариант: в левом поддереве ключи меньше узла, в правом больше. Поиск идёт от корня вниз и стоит O(h), где h это высота. Всё остальное зависит от высоты:

• обычное BST: в среднем при случайном порядке вставки O(log n), в худшем O(n). Вставьте отсортированные ключи, и дерево выродится в список;
• AVL: высоты поддеревьев отличаются не больше чем на единицу, дерево ниже, поиск чуть быстрее, зато больше поворотов при вставке и удалении;
• красно-чёрное: балансировка мягче, высота не больше 2·log₂(n+1), вставка и удаление дешевле. На нём построены TreeMap в Java и std::map в C++;
• B-дерево и B+-дерево: узел хранит сотни ключей, поэтому уровней мало. Для диска это главное: меньше уровней, меньше чтений страниц. Индексы PostgreSQL и MySQL устроены именно так;
• префиксное дерево (trie): поиск за O(k), где k длина ключа, удобно для автодополнения и роутинга.

У сбалансированных деревьев O(log n) гарантировано не только для поиска, но и для вставки и удаления.

Привязка к Go: упорядоченной мапы в стандартной библиотеке нет, встроенная map это хэш-таблица с O(1) в среднем и случайным порядком обхода. Если нужен порядок или поиск по диапазону, варианты такие: отсортированный слайс и slices.BinarySearch для редко меняющихся данных, github.com/google/btree с дженериками, своя реализация. С Go 1.23 обход дерева удобно отдавать итератором iter.Seq и перебирать через range.

Где спотыкаются

Отвечают «поиск в дереве O(log n)» без оговорки про баланс. Это верно только для сбалансированных деревьев.

Говорят, что каждый шаг отбрасывает ровно половину элементов. Так бывает лишь в идеально сбалансированном дереве, у красно-чёрного константа другая, хотя порядок тот же.

Не могут объяснить, зачем дерево, если есть хэш-таблица. Ответ: упорядоченный обход, диапазоны, поиск ближайшего ключа и предсказуемое худшее время.