Converting a 2-3-4 tree into a red black tree

Question

I'm trying to convert a 2-3-4 Tree into a Red-Black tree in java, but am having trouble figuring it out.

I've written these two basic classes as follows, to make the problem straightforward, but can't figure out where to go from here.

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;
    }
}

I'm assuming the 2-3-4 tree is valid, and want to return a red black tree when the method is called.

I've also tried the following code with no luck:

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 */)

etc. for keys.size() == 2, 1....

I know it has to be recursive in theory, but am having a hard time figuring it out. Any thoughts?

score 24 · Accepted Answer · answered Mar 28 '16 at 07:22

Consider these three rules:

Transform any 2-node in the 2-3-4 tree into a black node in the red-black tree.
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.
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.