Что такое «техника m-bridge» для разделения двоичных деревьев для параллельной обработки?

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 потомков.Вырежьте его из остальной части дерева.

Чтобы сделать много надрезов, несколько раз вырежьте самое большое оставшееся дерево.