将不平衡树转换为生成树

Question

如何将不平衡树转换为（平衡）生成树？假设我有一棵树（在不同的节点有不同的（不一定是不同的）数量的孩子）。我想操纵这棵树，使它成为一棵k-ary的生成树。

树上各种迭代是允许的。限制是我们不能只收集一个地方的所有节点，然后在其中创建一个生成树（这将是一个微不足道的方法）。相反，必须从给定的树创建生成树。也就是说，孩子可以与父母（和祖父母，如果需要的话）交换信息（例如，孩子节点的数量和孩子节点的ID），并且父母决定移动孩子之间的节点（按顺序以平衡树）。

你可能已经明白，我试图做到这一点在并行计算环境。其中，一个节点知道的是它的父节点，它的子节点以及每个子树中以子节点为根节点的节点数。

（家长和孩子会改变，因为我们努力平衡树）。有关如何解决这个问题的任何提示？

---

回复的意见，即为什么这个问题很重要/值得考虑 - 毕竟琐碎apporach是可伸缩的：

1. 从理论上来说是具有挑战性的开发使用为O较小（算法N）空间（用于平凡的方法）来构建生成树。

2. 有趣的是，考虑替代解决方案接近大规模。

3. 至于数字而言：N = 100,000（这是在今天的超级计算机常见，N将在即将到来的BG/Q 1000,000）。在所采用的简单方法步骤中，a）全部减少b）O（N）以构建生成树，并且c）最后进行一对多广播。

另一种分布式的方法可能不会给太大起色，但出curosity它可能是值得一试。

Answer 1

尊敬，我觉得你认真低估的程度，你的“琐碎的情况下”在一个典型的并行计算环境扩展。谨慎发布一些实际的数字？

Answer 2

在合适的算法的片某些随机沉思：

1. 选择一个“根”任意地，或许作为那些参加，或者与现有结构的根中具有最低索引的元素。
2. 将“相位”看作一个并行减少，计算树最深部分的深度和身份以及尚未饱和的树最浅部分。
3. 在每个阶段之后，根指导从最深部分到浅部分的正确数量的节点的移动以通过深度进行平衡。
4. 重复，直到完全平衡

这也可能在一个完全分布式的方式，其中每个居委会余额本身根据类似的AVL标准，并最终大的结构性变化，通过传播工作。