将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等等，请参考以下内容：

我知道理论上必须使用递归，但我难以理解。有什么想法吗？

- user3745602

Answer 1

考虑以下三个规则：

1. 将2-3-4树中的任何2节点转换为红黑树中的黑色节点。
2. 将3节点转换为子节点和父节点。 子节点有两个自己的孩子：W和X或X和Y。 父节点有另一个孩子：Y或W。 哪个项成为孩子，哪个项成为父项并不重要。 孩子为红色，父亲为黑色。
3. 将4节点转换为父节点和两个子节点，第一个子节点有自己的孩子W和X； 第二个子节点有孩子Y和Z。 和以前一样，孩子是红色的，父亲是黑色的。

如果遵循这些规则，则红黑规则会自动满足。 在应用变换后，以下是示例树的结果。 希望这能帮助您。如需易于理解和详细的解释，请参阅Robert Lafore的《数据结构》书籍。

- Yogesh Umesh Vaity