Необычная реализация на Java вставки красного/черного узла дерева

Я пишу программу для класса на Java, касающуюся красных/черных деревьев. Я хорошо понимаю, как они обычно работают, и должен использовать метод рекурсивной вставки. То, что я обычно использую, приведено ниже, чтобы соответствовать классу Node моего профессора. Что касается цвета, 0 — черный, 1 — красный. Предоставленный нам класс Node вообще не имеет дела с ключами.

private static void put(int val,  int col)
{ root = put(root, val, col); }

private static Node put(Node n, Integer val, int col)
{
    if (n == null){
        Node t=new Node(val);
        t.setColor(1);
        return t;
    }
    int cmp = val.compareTo(n.getValue());

    if (cmp < 0) n.setLeft(put(n.getLeft(), val, col));
    else if (cmp > 0) n.setRight(put(n.getRight(), val, col));
    else n.setColor(col);

    if (isRed(n.getRight()) && !isRed(n.getLeft())) n = rotateLeft(n);
    if (isRed(n.getLeft()) && isRed(n.getLeft().getLeft())) n = rotateRight(n);
    if (isRed(n.getLeft()) && isRed(n.getRight())) flipColors(n);
    return n;
}

Однако загвоздка в том, что мы должны возвращать логическое значение — если пользователь вставляет повторяющееся значение, которое уже есть в дереве, мы возвращаем false и не присоединяем узел. В противном случае мы присоединяем их и возвращаем true; код, предоставленный нам для этого, приведен ниже, но он не является рекурсивным (часть требований проекта). И хотя я не реализовал способ балансировки или вращения должным образом, возвращаемая логическая часть работает.

public boolean insertNode(Node node) {

    //Here is just an example of setting colors for a node. So far, it is in green color. But you need to modify the code to dynamically adjust the color to
    //either RED or BLACK according to the red-black logic 
    Node current_node;
    // if the root exists
    if (root == null) {
        root = node; // let the root point to the current node
        root.setColor(Node.BLACK);
        return true;
    } else {
        current_node = root;
        node.setColor(1);
        while (current_node != null) {
            int value = current_node.getValue();

            if (node.getValue() < value){ // go to the left sub-tree
                if (current_node.getLeft() != null) // if the left node is not empty
                    current_node = current_node.getLeft();
                else{ // put node as the left child of current_node
                    current_node.setLeft(node);
                    node.setParent(current_node);
                    current_node = null;    }   
                //System.out.println("Left:"+current_node); 
                }

            else if (node.getValue() > value){ // go to the right
                if (current_node.getRight() != null) // if the right node is not empty
                    current_node = current_node.getRight();
                else{ // put node as the right child of current_node
                    current_node.setRight(node);
                    node.setParent(current_node);
                    current_node = null;    }   
                //System.out.println("Right: "+current_node);   
                }

            else{
                //System.out.println("Else: "+current_node);
                return false;   }


            //if(current_node!=null&&current_node.getLeft()!=null&&current_node.getRight()!=null&&current_node.getLeft().isRed()&&current_node.getRight().isRed())
            //  flipColors(node);

        }
    }

    if(node.getParent()!=null){
        node=node.getParent();
        System.out.println("Case: node has parent, val="+node.getValue());
    }

    if(node.getLeft()!=null&&node.getRight()!=null){
        if((node.getRight().isRed())&&!node.getLeft().isRed())
            node=rotateLeft(node);
        if((node.getLeft().isRed())&&(node.getParent()!=null)&&(node.getParent().getLeft().getLeft()!=null)&&(node.getParent().getLeft().getLeft().isRed()))
            node=rotateRight(node);
        if((node.getLeft().isRed()) && (node.getRight().isRed()))
            flipColors(node);
    }
    return true;
}

Мне не удалось найти сопоставимые реализации в Интернете, и кажется, что логическое значение необходимо для правильной работы графического интерфейса программы. Если у кого-то есть хорошее предложение, с чего начать, я был бы признателен!


java red-black-tree-insertion red-black-tree
person 2rtmar    schedule 23.04.2018    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Для рекурсивного insertNode я предлагаю вам следующее: Создайте функцию insertNode(Node node, Node current_node), которая возвращает значение boolean. Идея состоит в том, чтобы всегда вызывать функцию insertNode для текущего исследуемого узла, начиная с корневого узла. Если узел не может быть немедленно добавлен в current_node, ответственный узел вызывается рекурсивно для обработки узла. Я предоставил вам короткий пример, основанный на вашем коде (с некоторыми комментариями, в чем заключается основная идея, очевидно, чего-то не хватает). Надеюсь, я правильно понял ваш вопрос, и это поможет вам в вашем понимании.

public boolean insertNode(Node node) {
    if (root == null) {
        root = node;
        root.setColor(Node.BLACK);
        return true;
    } else {
        boolean result = insertNode(node, root);

        if (result) {
            //Some other important stuff to do...
        }

        return result;
    }
}

public boolean insertNode(Node node, Node current_node) {
    int value = current_node.getValue();

    if (node.getValue() < value) {
        if (current_node.getLeft() != null) {
            // Investigate left
            return insertNode(node, current_node.getLeft());
        } else {
            // Insert node left
            return true;
        }
    } else if (node.getValue() > value) {
        if (current_node.getRight() != null) {
            // Investigate right
            return insertNode(node, current_node.getRight());
        } else {
            // Insert node right
            return true;
        }
    } else {
        return false;
    }
}
person Illedhar    schedule 23.04.2018

arrow_upward
0
arrow_downward

Теперь у меня есть рабочие функции, как показано ниже:

public boolean insertNode(Node node) {
    if(root==null){
        root=node;
        root.setColor(Node.BLACK);
        return true;
    }
    else
        node.setColor(Node.RED);

    return insertNode(node, root);

}

public boolean insertNode(Node node, Node cur){

    if(node.getValue()<cur.getValue()){

        if(cur.getLeft()!=null) 
            return insertNode(node, cur.getLeft());

        else{
            cur.setLeft(node);
            node.setParent(cur);
            handleInsertion(node);
            return true;    }   }

    else if(node.getValue()>cur.getValue()){

        if(cur.getRight()!=null)
            return insertNode(node, cur.getRight());

        else{
            cur.setRight(node);
            node.setParent(cur);
            handleInsertion(node);
            return true;    }   }
    else
        return false;
}
person 2rtmar    schedule 24.04.2018