Преобразование несбалансированного дерева в остовное дерево

Question

Как преобразовать несбалансированное дерево в (сбалансированное) остовное дерево? Предположим, у меня есть дерево (с разным (не обязательно разным) числом детей в разных узлах). Я хочу манипулировать деревом таким образом, чтобы оно превратилось в k-арное остовное дерево.

Разные итерации на дереве допускаются. Ограничение состоит в том, что мы не можем просто собрать все узлы в одном месте, а затем сделать из них остовное дерево (что было бы тривиальным способом сделать это). Скорее связующее дерево должно быть создано из данного дерева. То есть дети могут обмениваться информацией (например, количеством дочерних узлов и идентификаторами дочерних узлов) с родителем (и дедушкой, если требуется), и родитель принимает решение переместить узлы между своими детьми (по порядку сбалансировать дерево).

Возможно, вы поняли, что я пытаюсь сделать это в параллельной вычислительной среде. Где все, что знает узел, - это идентификатор его родителя, его дочерних элементов и количество узлов в каждом поддереве с дочерними элементами в качестве корня.

(Родитель и дети будут меняться, когда мы пытаемся сбалансировать дерево). Любой намек на то, как подойти к этой проблеме?

---

Ответьте на комментарий, почему эта проблема важна / заслуживает рассмотрения - ведь тривиальное приложение масштабируемо:

1. Теоретически сложно разработать алгоритм, который использует пространство меньше чем O(N) (используется в тривиальном подходе) для построения остовного дерева.

2. Интересно подумать об альтернативных подходах к решению в масштабе.

3. Что касается чисел: N=100000 (что является обычным в современных суперкомпьютерах, N будет 1000 000 в предстоящем BG/Q). В тривиальном подходе используются следующие этапы: а) все-редукция; б) O(N) для построения связующего дерева; в) и, наконец, широковещательная передача "один ко многим".

Альтернативный распределенный подход может не дать большого улучшения, но из любопытства стоит попробовать.

Answer 1

С уважением, я думаю, вы серьезно недооцениваете степень масштабирования вашего "тривиального случая" в типичной среде параллельных вычислений. Хотите опубликовать некоторые реальные цифры?

Answer 2

Несколько случайных размышлений о кусочках подходящего алгоритма:

1. Выберите "корень" произвольно, возможно, в качестве элемента с наименьшим индексом среди участвующих, или, возможно, в качестве корня существующей структуры.
2. Представьте себе "фазу" как одно параллельное сокращение, которое вычисляет глубину и идентичность самой глубокой части дерева и самой мелкой части дерева, которая еще не насыщена.
3. После каждой фазы корень направляет движение нужного количества узлов от самой глубокой части к мелкой части, чтобы сбалансировать по глубине.
4. Повторите, пока полностью не сбалансировано

Это также может работать полностью распределенным образом, где каждое соседство балансирует себя в соответствии с чем-то вроде критерия AVL, и в конечном итоге через него распространяются большие структурные изменения.