java - 将红黑树转换为 2, 4 树

Question

正如您可能已经猜到的那样，我正在尝试将 Java 中的红黑树转换为 2,4 树。我不太关注它是如何工作的，但更多的是找出遍历树的最佳方式。

将使用预先构建的红黑树，因此我必须以某种方式从每个节点收集信息，然后逐个节点构建新的 2,4 树。

我正在考虑使用基于数组的实现作为“过渡”阶段。例如，在 array[i] 中，其左子元素是 array[i(*2)]，其右子元素是 array[(i*2)+1)]。然后循环遍历数组并通过获取其信息(即它是否有红色或黑色子/ parent )从那里构建 2,4 并形成每个 2,4 节点。

这看起来效率很低，但到目前为止，这就是我所能想到的。

还有其他推荐吗？

Answer 1

看看this question .

具体来说，“带有两个黑色子节点的黑色节点是 2 节点，带有一个红色子节点的黑色节点是 3 节点，带有两个红色子节点的黑色节点是 4 节点” - 您可以直接使用它进行转换。