將紅黑樹轉換爲2,4樹

Question

因此，您可能已經猜到了我正嘗試將紅黑樹轉換爲Java中的2,4樹。我並沒有太在意這是如何工作的，而是更多的是找出遍歷樹的最佳方式。

要使用預先構建的紅黑樹，所以我必須以某種方式收集來自每個節點的信息，然後逐個構建新的2,4樹節點。

我正在考慮使用基於數組的實現，因爲我是一種'過渡'階段。因此，例如在數組[i]，其左邊的孩子是數組[我（* 2）]，其右邊的孩子是數組[[i * 2）+1）]。然後通過獲取信息（即，它是否有紅色或黑色的孩子/父母），並從中構建2,4個節點並形成每個2,4個節點。

這看起來效率很低，但到目前爲止，這是我所能想到的。

其他建議？

Answer 1

看看this question。

具體而言，「有兩個黑人孩子的黑人節點是2節點，一個紅孩子的黑節點是3節點，而有兩個紅孩子的黑節點是4節點」 - 您可以直接使用此節點轉換。