Преобразование дерева 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-узел в дереве 2-3-4 в черный узел в красно-черном дереве.
2. Преобразуйте любой 3-узел в дочерний узел и родительский узел. У дочернего узла есть два собственных дочерних элемента: либо W и X, либо X и Y. Родитель имеет еще одного дочернего элемента: либо Y, либо W. Не имеет значения, какой элемент становится дочерним, а какой - родительским. Ребенок окрашен в красный цвет, а родитель - в черный.
3. Преобразуйте любой 4-узел в родителя и двух потомков, у первого потомка есть свои потомки W и X; у второго ребенка есть дети Y и Z. Как и прежде, дети окрашены в красный цвет, а родитель - в черный.

Красно-черные правила автоматически выполняются, если вы будете следовать этим правилам. Вот результирующий пример дерева после применения преобразований.

Надеюсь, это поможет вам. Для простоты и подробного объяснения вы можете обратиться к книге Роберта Лафора "Структуры данных".