java - 2-3-4 ツリーを赤黒ツリーに変換する

Question

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

keys.size() == 2, 1....の場合など

理論的には再帰的でなければならないことは知っていますが、それを理解するのに苦労しています。何かご意見は？

score 21 · Accepted Answer

次の 3 つのルールを考慮してください。

2-3-4 ツリーの任意の2 ノードを赤黒ツリーの黒ノードに変換します。
任意の3 ノードを子ノードと親ノードに変換します。子ノードには、それ自身の 2 つの子 (W と X または X と Y) があります。親には、もう 1 つの子 (Y または W) があります。どちらの項目が子になり、どちらが親になるかは問題ではありません。子は赤、親は黒です。
任意の4 ノードを親と 2 つの子に変換します。最初の子には独自の子 W と X があります。2 番目の子には子 Y と Z があります。前と同様に、子は赤、親は黒です。