如何将不平衡树转换为(平衡)生成树？假设我有一棵树(不同节点上有不同(不一定不同)数量的子节点)。我想以这样的方式操作这棵树，使其成为 k 元生成树。
允许对树进行各种迭代。限制是我们不能只将所有节点收集在一个地方，然后用它们制作生成树(这将是一种简单的方法)。相反，生成树必须从给定的树创建。也就是说，子节点可以与父节点(以及祖 parent ，如果需要)交换信息(例如，它拥有的子节点数量和子节点的 id)，并且父节点决定在其子节点之间移动节点(按顺序)平衡树)。
你可能已经明白我正在尝试在并行计算环境中执行此操作。其中，节点所知道的只是其父节点的 id、子节点的 id 以及以其子节点为根的每个子树中节点的数量。
(当我们尝试平衡树时，父级和子级将会发生变化)。关于如何解决这个问题有任何提示吗？
回复为什么这个问题很重要/值得考虑的评论 - 毕竟这个简单的方法是可扩展的:
理论上，开发一种使用小于 O(N) 空间(在平凡方法中使用)来构建生成树的算法具有挑战性。
大规模思考替代解决方案很有趣。
就数字而言:N=100,000(这在当今的 super 计算机中很常见，在即将到来的BG/Q中N将是1000,000)。在简单的方法中，涉及的步骤是 a) 全归约 b) O(N) 构建生成树和 c) 最后是一对多广播。
另一种分布式方法可能不会带来太大的改进，但出于好奇，它可能值得尝试。
最佳答案
恕我直言，我认为您严重低估了您的“琐碎案例”在典型并行计算环境中的扩展程度。愿意发布一些实际数字吗？
关于algorithm - 将不平衡树转换为生成树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6011591/