Дублируйте / умножайте дерево эффективно
Мне нужна (для g ++) оптимизированная древовидная структура алгоритма (время вычислений) для дублирования / умножения дерева.
Мое дерево будет k-арным, но не обязательно заполненным.
Основная операция заключается в умножении (до k раз) существующего дерева и добавлении деревьев в качестве поддеревьев к новому узлу. Затем уровень конечного узла будет удален для хранения правила фиксированного уровня.
Кто-нибудь знает о структуре данных, предлагающей это?
Пример для умножения: предположим, у нас есть двоичное дерево
A
|
/ \
/ \
B C
| / \
| / \
D E F
и мы хотим добавить новый узел / умножить как
R
/ \
/ \
.. ..
Так что результат будет выглядеть
R
/ \
/ \
/ \
/ \
/ \
A A
| |
/ \ / \
/ \ / \
B C B C
| / \ | / \
| / \ | / \
D E F D E F
Я попытался организовать это в std :: vector в структуре, похожей на кучу, но умножение дерева все еще довольно медленное, потому что мне нужно копировать каждый уровень дерева отдельно, а не просто копировать все дерево сразу.
Решение
Когда вы добавляете R, тривиально дать ему два указателя на A, а не копировать все поддерево, начиная с A.
R
/ \
| |
\ /
A
|
/ \
/ \
B C
| / \
| / \
D E F
Это и очень быстро, и очень легко кодировать.
Теперь возникает проблема, если позже вы захотите обновить одну сторону дерева, но не другую. Например, возможно, вы хотите изменить «правильный» F на G. В этот момент вы можете использовать копирование при записи стратегия только на некоторых из узлов, в этом случае приводит к
R
/ \
/ \
A A <-- copied, left side points to B
| / \
/ \ * \
/ \ \
B C C <-- copied, left side points to E
| / \ / \
| / \ * \
D E F G
По сути, вам нужно всего лишь скопировать путь от точки изменения (F / G) до корневого (самый простой в реализации) или до самого высокого общего узла (A в этом примере).
Другие решения
Возможно взгляните на код Android для словаря T9. AFAIR выглядит плоско, но в основном они строят дерево букв, так что обход дерева сверху вниз создает слова. И я думаю, что они использовали относительные смещения для перехода от узла к следующему (например, связанный список).
Таким образом, вы должны быть в состоянии скопировать все дерево за один прогон.
Я не помню точную компоновку, и я думаю, что она не выглядела ужасно, как я здесь, но чтобы продолжить с вашим примером, это выглядело бы примерно (!) Примерно так:
# your tree
__________
/// _ \ _
/// /// \ \ /// \
A007021B007000D000000C007014E000000F000000
\\\_/ \\\_____/# copying it, "under" R:
__________ __________
_ /// _ \ _ /// _ \ _
/// \ /// /// \ \ /// \ /// /// \ \ /// \
R007049A007021B007000D000000C007014E000000F000000A007021B007000D000000C007014E000000F000000
\\\ \\\_/ \\\_____/ / \\\_/ \\\_____/
\\\______________________________________/