[解決済み】2-3-4ツリーを赤黒いツリーに変換する

質問内容

javaで2-3-4ツリーを赤黒ツリーに変換しようとしているのですが、うまくいきません。

問題をわかりやすくするために、この2つの基本クラスを以下のように書きましたが、これからどうすればいいのかがわかりません。

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

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

理論的には再帰的でなければならないことは分かっていますが、それを理解するのに苦労しています。何かアイデアはありますか？

どのように解決するのですか？

この3つのルールを考えてみましょう。

1. を変換してください。 2ノード の黒ノードに変換する。 赤黒い木
2. 任意の変換 3ノード を子ノードと親ノードに変換する。親ノードは 子ノードはそれ自身の2つの子、WとX、またはXとYのいずれかを持ちます。 親ノードは、YかWのどちらか1つの子を持つ。 のうち、どの項目が子になり、どの項目が親になるのか。子アイテムは は赤、親は黒に着色されます。
3. 任意の変換 4ノード を親と2人の子にし、最初の の子は自分の子WとXを持ち、2番目の子は子Yを持つ。 とZで構成されています。 黒

これらのルールに従えば、赤黒いルールは自動的に満たされます。以下は、変換を適用した結果のツリー例です。

これでうまくいけばいいのですが。わかりやすく詳しい説明は、Robert Laforeの「Data Structures」の本を参照してください。