Level 36, Lesson 08, Bonus 01

NodeHelperTestSolution.java

package com.javarush.test.level36.lesson08.bonus01;

import java.lang.reflect.Field;

public class NodeHelperTestSolution {

    public static void changeNode(String nodName, RedBlackTree tree, String fieldName, RedBlackTree.Node newValue) throws
            Exception
    {
        RedBlackTree.Node header = getFromTreeNodeByName(nodName, tree);
        setNewNodeValue(fieldName, newValue, header);
    }

    public static void setNewNodeValue(String fieldName, RedBlackTree.Node newValue, RedBlackTree.Node node) throws
            NoSuchFieldException, IllegalAccessException
    {
        Field nodeField = node.getClass().getDeclaredField(fieldName);
        nodeField.setAccessible(true);
        nodeField.set(node, newValue);
    }

    public static RedBlackTree.Node getNodeValue(String fieldName, RedBlackTree.Node node) throws
            NoSuchFieldException, IllegalAccessException
    {
        Field nodeField = node.getClass().getDeclaredField(fieldName);
        nodeField.setAccessible(true);
        return (RedBlackTree.Node) nodeField.get(node);
    }

    public static RedBlackTree.Node getFromTreeNodeByName(String nodName, RedBlackTree tree) throws
            NoSuchFieldException,
            IllegalAccessException
    {
        Field headerField = RedBlackTree.class.getDeclaredField(nodName);
        headerField.setAccessible(true);
        return (RedBlackTree.Node) headerField.get(tree);
    }

    public static void changeColor(RedBlackTree.Node node, RedBlackTree.Color newColor) throws Exception {
        Field colorField = node.getClass().getDeclaredField("color");
        colorField.setAccessible(true);
        colorField.set(node, newColor);
    }

    public static RedBlackTree.Node getEmptyNode() throws NoSuchFieldException, IllegalAccessException {
        Field field = RedBlackTree.class.getDeclaredField("EMPTY");
        field.setAccessible(true);
        return (RedBlackTree.Node) field.get(RedBlackTree.class);
    }
}

RedBlackTree.java

package com.javarush.test.level36.lesson08.bonus01;

public class RedBlackTree {
    protected Node current;
    private Node parent;
    private Node grand;
    private Node great;
    private Node header;


    private static final Node EMPTY = new Node(0);

    static {
        EMPTY.left = EMPTY;
        EMPTY.right = EMPTY;
    }

    public RedBlackTree() {
        header = new Node(Integer.MIN_VALUE);
        header.left = EMPTY;
        header.right = EMPTY;
    }

    public boolean isEmpty() {
        return header.right == EMPTY;
    }

    public void clear() {
        header.right = EMPTY;
    }

    public void insert(int item) {
        current = grand = parent = header;
        EMPTY.element = item;
        while (current.element != item) {
            great = grand;
            grand = parent;
            parent = current;
            current = item < current.element ? current.left : current.right;

            if (current.left.color == Color.RED && current.right.color == Color.RED) {
                reorient(item);
            }
        }

        if (current != EMPTY) {
            return;
        }

        current = new Node(item, EMPTY, EMPTY);

        if (item < parent.element) {
            parent.left = current;
        } else {
            parent.right = current;
        }

        reorient(item);
    }

    protected void reorient(int item) {
        current.color = Color.RED;
        current.left.color = Color.BLACK;
        current.right.color = Color.BLACK;

        if (parent.color == Color.RED) {
            grand.color = Color.RED;
            if (item < grand.element != item < parent.element) {
                parent = rotate(item, grand);
            }
            current = rotate(item, great);
            current.color = Color.BLACK;
        }

        header.right.color = Color.BLACK;
    }

    private Node rotate(int item, Node parent) {
        if (item < parent.element) {
            Node node = parent.left;
            Node resultNode = item < node.element ? rotateWithLeftNode(node) : rotateWithRightNode(node);
            parent.left = resultNode;
            return parent.left;
        } else {
            Node node = parent.right;
            Node resultNode = item < node.element ? rotateWithLeftNode(node) : rotateWithRightNode(node);
            parent.right = resultNode;
            return parent.right;
        }
    }

    private Node rotateWithLeftNode(Node element) {
        Node left = element.left;
        element.left = left.right;
        left.right = element;
        return left;
    }

    private Node rotateWithRightNode(Node element) {
        Node right = element.right;
        element.right = right.left;
        right.left = element;
        return right;
    }

    public static enum Color {
        BLACK,
        RED
    }

    public static class Node {
        private int element;
        private Node left;
        private Node right;
        private Color color;

        public Node(int element) {
            this(element, null, null);
        }

        public Node(int element, Node left, Node right) {
            this.left = left;
            this.right = right;
            this.element = element;
            this.color = Color.BLACK;
        }
    }
}

Solution.java

package com.javarush.test.level36.lesson08.bonus01;

/* Разбираемся в красно-черном дереве
Дана реализация красно-черного дерева.
Некоторые методы сломаны. Разберитесь в коде и исправьте ошибки.
Метод main не участвует в тестировании.
Все модификатры правильные.
Имена переменных и методов не изменяйте.
*/
public class Solution {
    public static void main(String[] args) {
    }
}