将不平衡树转换为生成树
如何将不平衡树转换为（平衡）生成树？假设我有一棵树（不同节点上有不同（不一定不同）数量的子节点）。我想以这样的方式操纵这棵树，使其成为一棵 k 元生成树。
允许对树进行各种迭代。限制是我们不能只将所有节点收集在一个地方，然后用它们制作生成树（这将是一种简单的方法）。相反，生成树必须从给定的树创建。也就是说，子节点可以与父节点（以及祖父母，如果需要）交换信息（例如，它拥有的子节点数量和子节点的 id），并且父节点决定在其子节点之间移动节点（按顺序）来平衡树）。
您可能已经明白我正在尝试在并行计算环境中执行此操作。其中，节点只知道其父节点的 id、子节点的 id 以及以子节点为根的每个子树中的节点数。
（当我们尝试平衡树时，父母和孩子会发生变化）。关于如何解决这个问题有任何提示吗？
回复为什么这个问题很重要/值得考虑的评论 - 毕竟平凡的方法是可扩展的：
理论上，开发一种使用小于 O(N) 空间（在平凡方法中使用）的算法来构建生成树。
大规模思考替代解决方案很有趣。
就数字而言：N=100,000（这在当今的超级计算机中很常见，在即将到来的BG/Q中N将是1000,000）。在简单的方法中，所涉及的步骤是 a) 全归约 b) O(N) 构建生成树 c) 最后是一对多广播。
另一种分布式方法可能不会带来太大的改进，但出于好奇，它可能值得尝试。
How to convert an unbalanced tree into a (balanced) spanning tree? Suppose I have a tree (with different (not necessarily distinct) number of children at different nodes). I want to manipulate the tree in such a way that it becomes a k-ary spanning tree.
Various iterations on the tree are allowed. The restriction is that we cannot just collect all the nodes at one place and then make a spanning tree out of them (which would be a trivial way to do). Rather the spanning tree has to be created from the given tree. That is the children can exchange information (e.g. the number of child nodes it has and the ids of the child nodes) with the parent (and the grandparent, if required) and the parent makes decision to move the nodes between its children (in order to balance the tree).
You may have understood that I am trying to do this in a parallel computing environment. Where, all a node knows is the id of its parent, its children and the number of nodes in each subtree with its children as the root.
(Parent and children will change as we try to balance the tree). Any hint on how to approach this problem?
Reply to the comment that why is this problem important/ worth considering - after all the trivial apporach is scalable:
Theoretically it is challenging to develop an algorithm that uses lesser than O(N) space(used in the trivial approach) to build the spanning tree.
It is interesting to think about alternative solution approaches at scale.
As far as numbers are concerned: N=100,000 (which is common in today's supercomputers, N will be 1000,000 in the upcoming BG/Q). In the trivial approach steps invloved are a) all-reduce b) O(N) to construct the spanning tree and c) and finally a one-to-many broadcast.
An alternative distributed approach may not give much improvement but out of curosity it may be is worth trying.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
恕我直言，我认为您严重低估了您的“琐碎案例”在典型并行计算环境中的扩展程度。愿意发布一些实际数字吗？
Respectfully, I think you're seriously underestimating the extent to which your "trivial case" scales in a typical parallel computing environment. Care to post some actual numbers?
对合适算法的一些随机思考：
这也可能以完全分布式的方式工作，其中每个邻域根据类似AVL标准的东西平衡自身，并最终传播大的结构变化。
Some random musings at the pieces of a suitable algorithm:
This might also work in a fully distributed fashion, where each neighborhood balances itself according to something like the AVL criterion, and eventually large structural changes propagate through.