将2-3-4树转换为红黑树

我正在尝试将 2-3-4 树转换为 java 中的红黑树，但我无法弄清楚它。

我将这两个基本类编写如下，以使问题简单明了，但不知道从这里到哪里去。

public class TwoThreeFour<K> {
    public List<K> keys;
    public List<TwoThreeFour<K>> children;
}

public class RedBlack<K> {
    public K key;
    public boolean isBlack;
    public RedBlack<K> left,right;
    public RedBlack<K key, boolean isBlack, RedBlack<K> left, RedBlack<K> right){
        this.key = key; this.isBlack = isBlack; this.left = left; this.right = right;
    }
}

我假设 2-3-4 树是有效的，并且希望在调用该方法时返回红黑树。

我也尝试过以下代码，但没有成功：

public convert(TwoThreeFour<K> tTF){
    if (ttf.keys.size() == 3)
        RedBlack<K> node = RedBlack<ttf.keys[1], true, RedBlack<ttf.keys[0], false, /* not sure what to put here for left */, /* not sure what to put here for right */), RedBlack<ttf.keys[2], false, /* not sure what to put here for left */, /* not sure what to put here for right */)

等等，对于keys.size() == 2, 1....

我知道理论上它必须是递归的，但我很难弄清楚它。有什么想法吗？

考虑以下三个规则：

1. Transform any 2-node in the 2-3-4 tree into a black node in the red-black tree.
2. Transform any 3-node into a child node and a parent node. The child node has two children of its own: either W and X or X and Y. The parent has one other child: either Y or W. It doesn’t matter which item becomes the child and which the parent. The child is colored red and the parent is colored black.
3. Transform any 4-node into a parent and two children, the first child has its own children W and X; the second child has children Y and Z. As before, the children are colored red and the parent is black.

The red-black rules are automatically satisfied if you follow these rules. Here's the resulting example tree after applying the transformations.

希望这能让你继续前进。为了易于理解和详细解释，可以参考Robert Lafore Data Structures一书。