Алгоритмы с нуля
Деревья: тест с выбором ответа
Суть Синтез юнита деревьев в формате выбора — структура узла, выбор traversal, инвариант BST, баланс и высота, BFS против DFS и паттерн tree DP.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небеШесть вопросов, проходящих сквозь весь юнит. Каждый — это решение, которое ты принимаешь, когда берёшь дерево в реальном коде: не определение для пересказа, а какой traversal, какой инвариант, какая сложность реально в игре.
Цель
Убедись, что ты связываешь структуру узла, выбор traversal, инвариант BST, баланс, BFS против DFS и паттерн tree DP — синтез, к которому вели отдельные уроки.
Викторина
Completed
Нужно вернуть значения binary search tree в порядке возрастания. Какой один traversal делает это напрямую и почему?
Heads-up Корень BST не медиана — это просто первое вставленное значение. Pre-order выдаёт корень раньше любого значения из левого поддерева, поэтому вывод не отсортирован. Только in-order даёт сортированный порядок.
Heads-up Level-order группирует узлы по глубине, а не по значению. Узел на глубине 1 может быть меньше или больше узла на глубине 2. Порядок BFS не связан с сортированным порядком в BST.
Heads-up Корень не минимум и не максимум BST. Post-order выдаёт оба ребёнка перед узлом, поэтому последовательность не отсортирована.
Викторина
Completed
Коллега вставляет ключи 1, 2, 3, 4, 5, 6, 7 в пустой BST именно в этом порядке, а затем жалуется, что поиск медленный. Что произошло и какова высота?
Heads-up Высота зависит от порядка вставки, а не только от числа узлов. Только сбалансированная форма даёт высоту ~log n; отсортированная вставка даёт цепочку высотой n-1.
Heads-up Инвариант (left < node < right) держится идеально — каждый узел больше своего родителя. Дерево — корректный BST; оно просто вырождено, и это проблема баланса, а не нарушение инварианта.
Heads-up Поиск не обходит всё дерево — он идёт по одному пути от корня к цели. Медленность это длина пути: в цепочке высотой 6 этот путь до 7 узлов, то есть O(n).
Викторина
Completed
Нужно сгруппировать каждый узел по его глубине — весь уровень 0, затем весь уровень 1 и так далее. Какой подход подходит и какова ключевая деталь реализации?
Heads-up In-order это обход в глубину: он спускается по левому хребту до того, как тронет правого ребёнка, поэтому узлы выходят перемешанными между уровнями. Пришлось бы группировать по глубине постфактум — BFS даёт группы по уровням напрямую.
Heads-up Посещение корня первым не даёт группировки по уровням. После корня pre-order ныряет во всё левое поддерево (все глубины) до того, как увидит правого ребёнка. DFS не может завершить уровень прежде, чем уйти глубже.
Heads-up Простой BFS даёт правильный порядок посещения, но не границы уровней. Без снимка размера в начале каждого уровня нельзя понять, где один уровень кончается и начинается следующий.
Викторина
Completed
В стандартном паттерне «рекурсия и комбинирование» для деревьев, что возвращает базовый случай для пустого поддерева при вычислении высоты (при соглашении, что лист имеет высоту 0)?
Heads-up Высота считает рёбра, а не узлы. Если бы null возвращал 0, лист вычислил бы 1 + max(0, 0) = 1, переоценив на единицу. Подсчёт узлов это другая задача с другим базовым случаем.
Heads-up Возврат null заставляет добавлять отдельную ветку при каждом комбинировании — именно этого числовой сентинел -1 (или 0 для подсчёта) и призван избежать. Смысл соглашения в единообразной арифметике.
Heads-up Это двойной счёт. Весь смысл выбора -1 для null в том, чтобы лист оказался на высоте 0 при заявленном в вопросе соглашении.
Викторина
Completed
При вычислении diameter binary tree (длиннейший путь между любыми двумя узлами) почему каждый рекурсивный вызов возвращает высоту поддерева, а diameter держится в боковой переменной?
Heads-up Если бы узел возвращал diameter, родитель не смог бы его продлить — путь через родителя использует высоту вниз одного ребёнка, а не полный diameter ребёнка. Это разные величины, поэтому паттерн их и разделяет.
Heads-up Два прохода (один для высот, один для diameter) обходят дерево дважды и заново выводят уже вычисленные высоты. Весь смысл tree DP в одном проходе: вернуть локальную информацию вверх, накопить глобальный ответ сбоку.
Heads-up Длиннейший путь может лежать целиком внутри поддерева и вообще не касаться корня. Именно поэтому максимум надо обновлять в каждом узле, а не только в корне.
Викторина
Completed
Два инженера сравнивают рекурсивный in-order traversal и level-order (BFS) обход одного и того же сбалансированного дерева с n узлами. Какова доминирующая дополнительная память каждого?
Heads-up Посещение n узлов это стоимость по времени, а не по памяти. Рекурсия держит только текущий путь от корня к узлу (O(h)); BFS держит только текущий фронт (O(w)). Ни тот, ни другой в общем случае не держит все n узлов сразу.
Heads-up Рекурсия расходует стек вызовов — один кадр на уровень на активном пути, то есть O(h). На вырожденном (цепочка) дереве это O(n) и может переполнить стек.
Heads-up Наоборот: глубина DFS ограничена высотой h (стек), а ширина BFS ограничена самым широким уровнем w (очередь). На сбалансированном дереве h ~ log n, а w ~ n/2.
Итог
Сквозная линия юнита — одно соответствие: форма данных диктует инструмент. Binary tree это узел с двумя поддеревьями, поэтому рекурсия — естественный обход; три порядка DFS различаются лишь тем, когда посещается узел, и in-order — тот, что читает BST отсортированным. Инвариант BST покупает поиск O(h) — но только баланс держит h около log n, а вставка в отсортированном порядке это худший случай, обрушивающий её в O(n). BFS со снимком размера на каждом уровне — инструмент, когда важна глубина, меняющий стек на очередь. А tree DP возвращает локальную информацию вверх, накапливая глобальный ответ сбоку — один проход, две величины.