Почему в некоторых случаях используется сбалансированное дерево вместо хэш-таблицы

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

Умеете ли вы выбирать структуру данных по набору нужных операций, а не по строчке из таблицы сложностей. В Go к этому добавляется знание своей стандартной библиотеки: карта там есть, упорядоченного контейнера нет, и надо понимать, чем его заменяют.

Как отвечать

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

• диапазонные запросы вида «все ключи от a до b», минимум, максимум, ближайший сосед сверху или снизу;
• обход в порядке ключей без пересортировки на каждом проходе;
• гарантия на худший случай: хэш-таблица при росте перестраивается, и отдельная вставка может занять заметно больше остальных, что бьёт по хвостовым задержкам;
• ключ, для которого есть только компаратор. В карту Go нельзя положить слайс, карту или функцию, а компаратор для составного ключа пишется руками.

Дальше стоит перевести это на практику Go. Дерева в стандартной библиотеке нет, поэтому выбор обычно такой: карта для точечного доступа, отсортированный слайс плюс slices.BinarySearch для данных, которые меняются редко, внешняя реализация B-дерева, когда данных много и они меняются постоянно.

keys := make([]string, 0, len(m))
for k := range m {
    keys = append(keys, k)
}
slices.Sort(keys)

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

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

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

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

Полагаются на порядок обхода карты, увидев его стабильным на десятке ключей. Обход в Go намеренно стартует со случайного места, так что на боевых данных порядок будет другим, а тест, который на него опирался, начнёт мигать.