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

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

score 21 · Accepted Answer

考虑以下三个规则：

将 2-3-4 树中的任意2 节点转换为红黑树中的黑色节点。
将任何3 节点转换为子节点和父节点。子节点有自己的两个子节点：W 和 X 或 X 和 Y。父节点还有另一个子节点：Y 或 W。哪个项目成为子节点和哪个父节点都没有关系。孩子是红色的，父母是黑色的。
将任意4 节点转换为一个父节点和两个子节点，第一个子节点有自己的子节点 W 和 X；第二个孩子有孩子 Y 和 Z。和以前一样，孩子是红色的，父母是黑色的。