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

Question

我试图在 java 中将 2-3-4 树转换为红黑树，但我无法弄清楚。

我已经把这两个基本的类写成如下，使问题简单明了，但无法弄清楚从这里去哪里。

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 树是有效的，并且希望在调用该方法时 return 红黑树。

我也尝试过以下代码但没有成功：

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

考虑这三个规则：

将2-3-4树中的任意2-node变换为 red-black 树。
将任何3-节点转换为child节点和parent节点。这 child 节点有两个自己的 children：要么是 W 和 X，要么是 X 和 Y。 parent 还有一个 child：Y 或 W。没关系哪个项目成为 child，哪个项目成为 parent。 child 是颜色为红色，parent 颜色为黑色。
将任意4-node转化为一个parent和两个children，第一个 child有自己的child任W和X；第二个 child 有 children Y 和 Z。和以前一样，children 是红色的，parent 是黑色的。

如果您遵循这些规则，red-black 规则将自动得到满足。这是应用转换后生成的示例树。

希望这能让你继续前进。为了易于理解和详细解释，您可以参考Robert Lafore的Data Structures一书。

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

Converting a 2-3-4 tree into a red black tree

java

tree

red-black-tree

2-3-4-tree