← All posts tagged algorithms

Чего-то сильно туплю и не могу правильно "задизайнить" алгоритм.

Есть дерево, можно считать, что rose tree, узлы в дереве могут быть протегированы (т.е. ему сопоставляется булевый флаг).
"интересной областью" назовём поддерево между двумя соседними тегированными узлами при проходе сверху-вниз-слева-направо (depth-first в общем-то). Нужно построить список поддеревьев, такой, чтобы в каждом поддереве была только одна "интересная область" + периферия — узлы не входящие ни в одну интересную область. Вот это делается достаточно просто.

Но оказалось, что это не совсем то, что нужно, а на самом деле интересует "интересная область"* — эта область между двумя тегированными узлами находящимися на одной и той же глубине. И вот как эффективно получить такое представление мне не понятно.

Идеи? Картинки могу нарисовать в принципе, но лень.

Принимаются: словесное описание алгоритма, ссылки на конкретные главы конкретной книги, работающий код, петросянство.