2

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

允许对树进行各种迭代。限制是我们不能只在一个地方收集所有节点，然后用它们制作生成树（这将是一种简单的方法）。而是必须从给定的树创建生成树。也就是说，子节点可以与父节点（以及祖父节点，如果需要）交换信息（例如，它拥有的子节点的数量和子节点的 ID），并且父节点决定在其子节点之间移动节点（按顺序平衡树）。

您可能已经理解我正在尝试在并行计算环境中执行此操作。其中，节点只知道其父节点的 id、子节点以及每个以子节点为根的子树中的节点数。

（当我们试图平衡树时，父母和孩子会改变）。关于如何解决这个问题的任何提示？

回复为什么这个问题很重要/值得考虑的评论 - 毕竟微不足道的方法是可扩展的：

  1. 从理论上讲，开发一种使用小于 O(N) 空间（在普通方法中使用）来构建生成树的算法具有挑战性。

  2. 大规模考虑替代解决方案很有趣。

  3. 就数字而言：N=100,000（这在当今的超级计算机中很常见，在即将到来的 BG/Q 中 N 将是 1000,000）。在简单的方法中，涉及的步骤是 a) all-reduce b) O(N) 来构造生成树和 c) 最后是一对多广播。

另一种分布式方法可能不会带来太大改进，但出于好奇，它可能值得尝试。

4

2 回答 2

2

尊敬的，我认为您严重低估了您的“琐碎案例”在典型并行计算环境中的扩展程度。愿意发布一些实际数字吗？

于 2011-05-15T22:59:58.940 回答
1

对合适算法的一些随机思考：

  1. 任意选择一个“根”，可能是参与的元素中索引最低的元素，也可能是现有结构的根。
  2. 将“阶段”视为一种并行缩减，它计算树的最深部分和尚未饱和的树的最浅部分的深度和身份。
  3. 在每个阶段之后，根引导正确数量的节点从最深部分移动到浅部分，以按深度平衡。
  4. 重复直到完全平衡

这也可能以完全分布式的方式发挥作用，其中每个邻域根据 AVL 标准之类的东西自我平衡，并最终传播大的结构变化。

于 2011-05-16T02:31:01.850 回答