Алгоритмы с нуля
Деревья: собери BST-тулкит
Ты ходил по деревьям, упорядочивал их и гонял tree DP на бумаге. Теперь собери тулкит сам: binary search tree, который вставляет, ищет, обходит четырьмя способами, валидирует собственный инвариант и сообщает свой diameter и баланс. Тесты — то место, где краевые случаи юнита (вырожденные деревья, границы предков, высоты листьев) перестают быть мелочью и становятся кодом, который либо проходит, либо падает.
Преврати ментальную модель юнита в работающую протестированную библиотеку структуры данных: реализуй вставку и поиск BST, все четыре traversal, корректный (с границей диапазона) валидатор BST и метрики tree DP — высоту, diameter и баланс — затем докажи каждую тестами, включая вырожденный худший случай, ломающий O(log n).
Реализуй самодостаточную библиотеку binary search tree на языке по выбору, предоставляющую insert, search, четыре traversal, корректный валидатор BST и метрики tree DP — подкреплённую набором тестов, демонстрирующим и счастливый путь, и вырожденный худший случай.
- Все traversal возвращают правильную последовательность на нарисованном от руки примере дерева, сверенную с собственной трассировкой на бумаге.
- isValidBST возвращает false для намеренно невалидного дерева и true для любого валидного BST, построенного через insert — тест на баг локальной проверки проходит.
- height, diameter и isBalanced совпадают с вычисленными вручную значениями хотя бы на двух деревьях — одном сбалансированном и одном перекошенном.
- Тест на отсортированную вставку показывает высоту n-1, демонстрируя вырожденный худший случай, с однострочной заметкой, почему баланс (AVL/red-black) это починил бы.
- Добавь delete(value), обрабатывающий все три случая (лист, один ребёнок, два ребёнка через in-order преемника), и протестируй, что инвариант BST всё ещё держится после через isValidBST.
- Реализуй итеративный in-order traversal с явным стеком (без рекурсии) и убедись, что он даёт последовательность, идентичную рекурсивной версии.
- Добавь самобалансирующуюся вставку (повороты AVL или red-black) и перезапусти тест на отсортированную вставку, чтобы показать, что высота остаётся O(log n) там, где у простого BST было O(n).
- Добавь maxPathSum (tree DP, допускающий отрицательные значения узлов и любой путь узел-к-узлу) и сверь его на дереве с отрицательными значениями, где оптимальный путь пропускает поддерево.
Это та петля, что стоит за каждой задачей про деревья, которую ты ещё встретишь: узел это значение плюс два поддерева, поэтому insert, search и traversal — всё это рекурсия по этой форме; корректность инварианта BST требует передаваемого от предков диапазона, а не локального взгляда; высота, diameter и баланс — это tree DP за один проход с возвращаемым значением, отличным от ответа; а вырожденный случай отсортированной вставки — напоминание, что инвариант гарантирует порядок, а не баланс. Один раз собрав и протестировав это, ты доводишь до автоматизма и версию для интервью, и продакшен-версию.