Сжатие префиксного дерева.
Переменные:
n - кол-во узлов дерева.
deep - реальная глубина дерева.
startNode - начальный узел.
Поиск реальной глубины(deep).
Для начала стоит найти реальную глубину дерева, для того чтобы нивелировать потери, а также улучшить последующие сжатия.
Осуществлять поиск будем с помощью DFS. Проще говоря пройдем по всем узлам дерева, замеряя при этом длину от нулевого узла. Результатом поиска будет индекс узла с максимальным удалением от нулевого узла. (startNode)
Пример:
Результатом работы алгоритма будет 10_a:
Сложность: O(n).
Структура хранения графа.
Граф будет создан с помощью указателей и будет хранить внутри себя Node(В которой храниться индекс буквы(от нуля до двух) и кол-во этих букв, и 2 bool перменных, которая будет обозначать какое сжатие было в этом узле(isWidth, isDeep)) и Edge(В которой храниться ссылка на прошлый Node и ссылка на следующий)
Сжатие глубины дерева.
С помощью BFS проходим по дереву, при этом контролируя глубину дерева, с помощбю сепараторов(Добавлять сепаратор в конец очереди, и как только мы достигли сепаратора, значит все узлы этой глубины пройдены). Также при этом транслируя дерево в новую структуру данных, описанную сверху.
Сжатие дерева будет проходить при условии, что нет разветлений, т.е. простая линия.
Пример:
До сжатия:
После:
Сложность: O(n).
Срывание листов с дерева.
Проходим по новосозданному дереву с помощью BFS. Как только находим два и более одинаковых листа, сокращаем их, удаляя связи и увеличивая значение в Node
Пример:
До сжатия:
После:
Сложность: O(n).
Проблемы
Деревья, где есть исключительно развилки, как например бинарные деревья, мало поддаются сжатию.
Итог
Таким образом можно без потерь сжать некоторые деревья в несколько раз. Сложность примерно: O(3n).