什么是分割二叉树进行并行处理的“m-桥技术”？

Question

它是如何工作的？请用英文或伪代码详细解释，以便我可以用任何语言实现。

要提到的和本文简要介绍： http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.4.3643&rep=rep1&type=pdf

，但没有足够的细节没有落实自己。 （图2b中的权重看起来不对，并且不清楚他们如何决定图2c中的切入点）。

我也查了原始源文件（http://www-2.cs.cmu.edu/~glmiller/Publications/Papers/ReMiMo93.pdf），但无法从那里找出结果。

是否有更好的算法满足相同的需求？具体来说，任何可以保证“几乎相同大小”（但更重要）的分区树的东西？本文提出m-bridge保证没有分区树大于4n/p，如果只有4个处理器，这并不是太大的保证！

Answer 1

为了一个斩：

1. 对于树中的每个节点，计算有多少的后裔节点。
2. 具有> n/2个后代的节点形成一条下降路径。下降到路径的底部。
3. 其中一个孩子有n/3和n/2后代之间。把它从树的其余部分剪下来。

要进行多次切割，请反复切割剩下的最大树。