Convert 2-3-4 wood to red ebony

Question

I am trying to convert a 2-3-4 tree to a Red-Black tree in java, but it is hard for me to understand it.

I wrote these two main classes as follows to make the problem simple, but I cannot 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 assume that the 2-3-4 tree is valid and wants to return the red ebony when the method is called.

I 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 that it should be recursive in theory, but it's hard for me to understand it. Any thoughts?

Answer 1

Consider these three rules:

• 2- node 2-3-4 node - .
• 3- node node node. node : W, X, X Y. : Y, W. . , .
• 4- node , W X; Y Z. , , .

- , . .

, . Robert Lafore Data Structures.