javatreered-black-tree2-3-4-tree

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

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?

Solution

  • Consider these three rules:

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

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

    Hopefully that should get you going. For easy to understand and detailed explanation, you can refer to Robert Lafore's Data Structures book.