обходы дерева
Dec. 28th, 2022 12:22 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
amaraoА вот я думал, что задачу symmetric tree я решу в пол-пинка. (Задача: по заданному дереву сказать, симметричное ли оно).
Теоретическое решение: pre_walk() == post_walk().
Практические проблемы: наивные методы обхода дерева используют рекурсию, а использовать рекурсию при параллельном обходе дерева двумя разными способами - себе дороже.
Выгрузка обоих деревьев в список и сравнение - уровень сложности алгоритма `o(позор)`.
Правильное решение: реализовать стеки из вектора и обходить в цикле. Но два обхода в одной функции уродливо, так что идиоматический подход должен реализовать итератор pre_walk(), итератор post_walk(), и потом просто сравнить их. (то есть решение будет `pre_walk(&tree) == post_walk(&tree)`).
А вот над реализацией нерекурсивного обхода дерева я сейчас буду думать. Теоретически, ничего сложного, но масса эргономических нюансиков (например, как хранить направление движения (влево или вправо)? Надо ли его хранить или оно само получится?).
Плюс rust'овая машинерия для итераторов, которая выглядит ясной и простой, пока туда lifetimes для захваченных ref не появятся.
Короче, задача сводится к pre_order walk через итератор. Решу её, дальше тривиально. Традиционно, сначала решаю, потом читаю умные тексты.
Теоретическое решение: pre_walk() == post_walk().
Практические проблемы: наивные методы обхода дерева используют рекурсию, а использовать рекурсию при параллельном обходе дерева двумя разными способами - себе дороже.
Выгрузка обоих деревьев в список и сравнение - уровень сложности алгоритма `o(позор)`.
Правильное решение: реализовать стеки из вектора и обходить в цикле. Но два обхода в одной функции уродливо, так что идиоматический подход должен реализовать итератор pre_walk(), итератор post_walk(), и потом просто сравнить их. (то есть решение будет `pre_walk(&tree) == post_walk(&tree)`).
А вот над реализацией нерекурсивного обхода дерева я сейчас буду думать. Теоретически, ничего сложного, но масса эргономических нюансиков (например, как хранить направление движения (влево или вправо)? Надо ли его хранить или оно само получится?).
Плюс rust'овая машинерия для итераторов, которая выглядит ясной и простой, пока туда lifetimes для захваченных ref не появятся.
Короче, задача сводится к pre_order walk через итератор. Решу её, дальше тривиально. Традиционно, сначала решаю, потом читаю умные тексты.