將不平衡樹轉換爲生成樹

Question

如何將不平衡樹轉換爲（平衡）生成樹？假設我有一棵樹（在不同的節點有不同的（不一定是不同的）數量的孩子）。我想操縱這棵樹，使它成爲一棵k-ary的生成樹。

樹上各種迭代是允許的。限制是我們不能只收集一個地方的所有節點，然後在其中創建一個生成樹（這將是一個微不足道的方法）。相反，必須從給定的樹創建生成樹。也就是說，孩子可以與父母（和祖父母，如果需要的話）交換信息（例如，孩子節點的數量和孩子節點的ID），並且父母決定移動孩子之間的節點（按順序以平衡樹）。

你可能已經明白，我試圖做到這一點在並行計算環境。其中，一個節點知道的是它的父節點，它的子節點以及每個子樹中以子節點爲根節點的節點數。

（家長和孩子會改變，因爲我們努力平衡樹）。有關如何解決這個問題的任何提示？

---

回覆的意見，即爲什麼這個問題很重要/值得考慮 - 畢竟瑣碎apporach是可伸縮的：

1. 從理論上來說是具有挑戰性的開發使用爲O較小（算法N）空間（用於平凡的方法）來構建生成樹。

2. 有趣的是，考慮替代解決方案接近大規模。

3. 至於數字而言：N = 100,000（這是在今天的超級計算機常見，N將在即將到來的BG/Q 1000,000）。在所採用的簡單方法步驟中，a）全部減少b）O（N）以構建生成樹，並且c）最後進行一對多廣播。

另一種分佈式的方法可能不會給太大起色，但出curosity它可能是值得一試。

Answer 1

尊敬，我覺得你認真低估的程度，你的「瑣碎的情況下」在一個典型的並行計算環境擴展。謹慎發佈一些實際的數字？

Answer 2

在合適的算法的片某些隨機沉思：

1. 選擇一個「根」任意地，或許作爲那些參加，或者與現有結構的根中具有最低索引的元素。
2. 將「相位」看作一個並行減少，計算樹最深部分的深度和身份以及尚未飽和的樹最淺部分。
3. 在每個階段之後，根指導從最深部分到淺部分的正確數量的節點的移動以通過深度進行平衡。
4. 重複，直到完全平衡

這也可能在一個完全分佈式的方式，其中每個居委會餘額本身根據類似的AVL標準，並最終大的結構性變化，通過傳播工作。