RB Tree

package adt.rbtree;

import adt.bst.BSTImpl;
import adt.bst.BSTNode;
import adt.rbtree.RBNode.Colour;

public class RBTreeImpl<T extends Comparable<T>> extends BSTImpl<T>
        implements RBTree<T> {

    public RBTreeImpl() {
        this.root = new RBNode<T>();
    }

    protected int blackHeight() {
        // TODO Implement your code here
        throw new UnsupportedOperationException("Not implemented yet!");
    }

    protected boolean verifyProperties() {
        boolean resp = verifyNodesColour() && verifyNILNodeColour()
                && verifyRootColour() && verifyChildrenOfRedNodes()
                && verifyBlackHeight();

        return resp;
    }

    /**
     * The colour of each node of a RB tree is black or red. This is guaranteed
     * by the type Colour.
     */
    private boolean verifyNodesColour() {
        return true; // already implemented
    }

    /**
     * The colour of the root must be black.
     */
    private boolean verifyRootColour() {
        return ((RBNode<T>) root).getColour() == Colour.BLACK; // already
                                                                // implemented
    }

    /**
     * This is guaranteed by the constructor.
     */
    private boolean verifyNILNodeColour() {
        return true; // already implemented
    }

    /**
     * Verifies the property for all RED nodes: the children of a red node must
     * be BLACK.
     */
    private boolean verifyChildrenOfRedNodes() {
        return this.verifyChildrenOfRedNodes((RBNode<T>) this.root);
    }

    private boolean verifyChildrenOfRedNodes(RBNode<T> node) {
        if(node.isLeaf()) return true;

        boolean left;
        boolean right;
        if(node.getColour().equals(Colour.RED)) {
            if(node.getLeft().equals(Colour.RED)) return false;
            if(node.getRight().equals(Colour.RED)) return false;
        }

        left = this.verifyChildrenOfRedNodes((RBNode<T>)node.getLeft());
        right = this.verifyChildrenOfRedNodes((RBNode<T>) node.getRight());

        return left && right;
    }

    /**
     * Verifies the black-height property from the root. The method blackHeight
     * returns an exception if the black heights are different.
     */
    private boolean verifyBlackHeight() {
        if(!this.root.isEmpty()) {
            return blackHeight((RBNode<T>) this.root.getLeft()) == blackHeight((RBNode<T>) this.root.getRight());
        }
        return true;
    }

    private int blackHeight(RBNode<T> node) {
        if(node.isEmpty()) return 1;

        if(node.getColour().equals(Colour.BLACK)) return 1 + blackHeight( (RBNode<T>)node.getLeft()) + blackHeight((RBNode<T>)node.getRight());
        else return blackHeight( (RBNode<T>)node.getLeft()) + blackHeight((RBNode<T>)node.getRight());
    }

    @Override
    public void insert(T value) {
        super.insert(value);
        RBNode<T> node = (RBNode<T>)super.search(value);
        node.setColour(Colour.RED);
        this.fixUpCase1(node);
    }

    @Override
    public RBNode<T>[] rbPreOrder() {
        RBNode<T>[] arr = new RBNode[this.size()];
        if(!this.isEmpty()) rbpreOrder((RBNode<T>) this.root, arr, 0);
        return arr;
    }

    private int rbpreOrder(RBNode<T> no, RBNode<T>[] arr, int idx) {
        if(!no.isEmpty()) {
            arr[idx++] = no;
            idx = rbpreOrder((RBNode<T>) no.getLeft(), arr, idx);
            idx = rbpreOrder((RBNode<T>) no.getRight(), arr, idx);
        }
        return idx;
    }

    public RBNode<T> leftRotation(RBNode<T> node) {
        RBNode y = (RBNode)node.getRight();

        if(node.getParent() != null) {
            if(node.getParent().getRight().equals(node)) node.getParent().setRight(y);
            else node.getParent().setLeft(y);
        }
        y.setParent(node.getParent());
        node.setParent(y);
        if(y.getLeft() != null) {
            node.setRight(y.getLeft());
            y.getLeft().setParent(node);
        }
        y.setLeft(node);

        return y;

    }

    public RBNode<T> rightRotation(RBNode<T> node) {
        RBNode y = (RBNode)node.getLeft();

        if(node.getParent() != null) {
            if(node.getParent().getLeft().equals(node)) node.getParent().setLeft(y);
            else node.getParent().setRight(y);
        }

        y.setParent(node.getParent());
        node.setParent(y);
        if(y.getRight() != null) {
            node.setLeft(y.getRight());
            y.getRight().setParent(node);
        }
        y.setRight(node);

        return y;
    }

     protected void toLeft(RBNode<T> node) {
            RBNode<T> center = leftRotation(node);
            if(node.equals(this.root)) this.root = center;
        }

        protected void toRight(RBNode<T> node) {
            RBNode<T> center = rightRotation(node);
            if(node.equals(this.root)) this.root = center;
        }
    // FIXUP methods
    protected void fixUpCase1(RBNode<T> node) {
        if(node.equals(root)) ((RBNode<T>) this.root).setColour(Colour.BLACK);
        else fixUpCase2(node);
    }

    protected void fixUpCase2(RBNode<T> node) {
        if(!((RBNode<T>)node.getParent()).getColour().equals(Colour.BLACK)) {
            this.fixUpCase3(node);
        }
    }

    protected void fixUpCase3(RBNode<T> node) {
        RBNode<T> tio = (RBNode<T>) node.getParent().getParent();
        if(tio.getLeft().equals(node.getParent())) tio = (RBNode<T>) tio.getRight();
        else tio = (RBNode<T>) tio.getLeft();

        if(tio.getColour().equals(Colour.RED)) {
            ((RBNode<T>)node.getParent()).setColour(Colour.BLACK);
            tio.setColour(Colour.BLACK);
            ((RBNode<T>)tio.getParent()).setColour(Colour.RED);
            this.fixUpCase1(node);
        }else this.fixUpCase4(node);
    }

    protected void fixUpCase4(RBNode<T> node) {
        RBNode<T> next = node;
        RBNode<T> pai = (RBNode<T>)node.getParent();
        if(pai.getParent().getLeft().equals(pai)) {
            if(pai.getRight().equals(node)){
                this.toLeft(pai);
                next = (RBNode<T>) node.getLeft();
            }
        }else {
            if(pai.getLeft().equals(node)) {
                this.toRight(pai);
                next = (RBNode<T>) node.getRight();
            }
        }

        this.fixUpCase5(next);
    }

    protected void fixUpCase5(RBNode<T> node) {
        RBNode<T> pai = (RBNode<T>) node.getParent();
        pai.setColour(Colour.BLACK);

        RBNode<T> avo = (RBNode<T>) node.getParent().getParent();

        if(pai.getRight().equals(node)){
            this.toLeft(avo);
        }else this.toRight(avo);
    }
}