我需要(对于 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 时,给它 2 个指向 A 的指针而不是复制从 A 开始的整个子树是微不足道的。
R
/ \
| |
\ /
A
|
/ \
/ \
B C
| / \
| / \
D E F
这既非常快又非常容易编码。
现在,如果您以后想要更新树的一侧而不是另一侧,那么这里的障碍就来了。例如,也许您想将“正确的”F 更改为 G。此时您可以使用 copy-on-write仅在某些节点上的策略,在这种情况下导致
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)的路径。
关于c++ - 有效地复制/乘法树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16053717/