Быстрый поиск — главная задача структур данных. Двоичный поиск и деревья поиска находят элемент за логарифм, а хеш-таблица — в среднем мгновенно; у каждой из этих идей свои условия и ловушки.
Что нужно знать
- Последовательный поиск — $O(n)$; двоичный — $O(\log n)$, только в отсортированном массиве; для $n$ элементов не больше $\lceil \log_2(n+1) \rceil$ сравнений.
- Двоичное дерево поиска: в левом поддереве ключи меньше, в правом — больше.
- Минимум — самый левый узел, максимум — самый правый.
- Удаление: лист — просто убрать; один потомок — заменить им; два — заменить на преемника (минимум правого поддерева).
- Обходы: прямой (корень–лево–право), симметричный (лево–корень–право, даёт сортированный порядок), обратный (лево–право–корень).
- Вырожденное дерево превращается в список ($O(n)$); АВЛ- и splay-деревья поддерживают балансировку.
- Хеш-таблица: ключ → хеш → ячейка; коллизии решают цепочками или открытой адресацией; коэффициент заполнения = элементов / ячеек.
Где чаще всего ошибаются
- Применять двоичный поиск к неотсортированному массиву.
- Путать симметричный обход с прямым.
- Считать, что дерево поиска всегда даёт $O(\log n)$ без балансировки.
Проверить себя
По этой же теме курса есть проверочная работа из 15 заданий на 30 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Программирование (ИТ-класс) · 10–11 классы · Поиск, деревья поиска и хеширование