将2-3-4树转换为红黑树

Question

我正在尝试将2-3-4树转换为java中的红黑树,但我很难搞清楚它.

我写了这两个基本类如下,以使问题简单明了,但无法弄清楚从哪里开始.

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 ... ....

我知道它必须在理论上是递归的,但我很难搞清楚它.有什么想法吗？

Answer 1

考虑以下三个规则:

1. 将2-3-4树中的任何2节点转换为红黑树中的黑色节点.
2. 将任何3节点转换为子节点和父节点.子节点有两个子节点:W和X或X和Y.父节点有另一个子节点:Y或W.哪个项目成为子节点和哪个子节点无关紧要.孩子身着红色,父母身着黑色.
3. 将任何4节点转换为父节点和两个子节点,第一个子节点有自己的子节点 W和X; 第二个孩子有孩子Y和Z.和以前一样,孩子们都是红色,父母是黑人.

如果您遵循这些规则,则会自动满足红黑规则.这是应用转换后生成的示例树.

希望这能让你前进.为了便于理解和详细解释,您可以参考Robert Lafore的数据结构书.