什麼是分割二叉樹進行並行處理的「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後代之間。把它從樹的其餘部分剪下來。

要進行多次切割，請反覆切割剩下的最大樹。