Выбор ответа Junior Деревья спрашивают часто обновлено
Поиск в BST
Вопрос
Какая сложность поиска в бинарном дереве поиска?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: O(h): O(log n) у сбалансированного, O(n) в худшем. Поиск спускается от корня до листа: число шагов равно высоте.
Варианты ответа
- Всегда O(log n): каждый шаг отбрасывает половину
- O(h): O(log n) у сбалансированного, O(n) в худшемправильный ответ
- Всегда O(n): в худшем случае обходится всё дерево
- O(1) в среднем, как у хеш-таблицы с ключами
Разбор
Поиск спускается от корня до листа: число шагов равно высоте. Если вставлять отсортированные данные в простое BST, оно выродится в список и высота станет n. Сбалансированные деревья (AVL, красно-чёрные) гарантируют O(log n).
- «Всегда O(log n)» верно только для сбалансированных.
- O(n) лишь худший случай.
- O(1) это хеш-таблица в среднем.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.