rbt

public class RBTree <Key extends Comparable<Key>> {

    private static final boolean RED   = true;
    private static final boolean BLACK = false;

    Node root;


    /* 1)jesli puste to dodajemy jako czarny korzeń
     * 2)else{ skladamy na prawo/lewo w zaleznosci od wielkosci
     *   a) if parent is black OK!
     *   b) if parent is red
     *      -if black or absent sibling = rotuj
     *      -if red sibling, recolour & check again
     */
    //NO LINK TO PARENT

    public RBTree(){
    	root=null;
    }

    private boolean isRed( Node x){
    	return x!= null && x.color==RED;
    	}


    public void insert(Key key){
    	root = insert(key, root);
    	root.color=BLACK;
    }


    public Node insert(Key key, Node aktualny) {
    	/*if (root == null) {
    		root = new Node(key);

    	}*/
    	if(aktualny == null){
    		return new Node(key);
    	}
    		//aktualny = root;
    		//while(true){
    		int comp = key.compareTo(aktualny.key);
    		//jesli wstawiany<aktualnego
    		if(comp<0)
    			aktualny.left=insert(key,aktualny.left);
    		else if(comp>0)
    			aktualny.right=insert(key,aktualny.right);

    		else throw new RuntimeException("Duplicate"+key.toString());

    		//break;}

    		if (isRed(aktualny.left)  &&  isRed(aktualny.left.left))
    			aktualny.color=RED;
    			aktualny.left.color=BLACK;
    			aktualny = rotateR(aktualny);

    		if (isRed(aktualny.right)  &&  isRed(aktualny.right.right))
    			aktualny.color=RED;
    			aktualny.right.color=BLACK;
    			aktualny = rotateL(aktualny);

    		if (isRed(aktualny.left)  &&  isRed(aktualny.left.right))
    			aktualny.color=RED;
    			aktualny.left.right.color=BLACK;
    			aktualny.left = rotateL(aktualny.left);
    			aktualny = rotateR(aktualny);

    		if( isRed( aktualny.right ) && isRed( aktualny.right.left ) ) {
    			aktualny.color =RED ;
    			aktualny.right.left.color = BLACK ;
    			aktualny.right= rotateR(aktualny.right);
    			aktualny = rotateL( aktualny );
    		}

    		if (isRed(aktualny.left)  &&  isRed(aktualny.right))
    			colorFlip(aktualny);




		return aktualny;
    }

    /*public int zewn(Node aktualny){
    	if(aktualny == null) return 1;
    	return aktualny.key = zewn(aktualny.left)+zewn(aktualny.right);
    }*/

    private void colorFlip(Node aktualny){
    aktualny.color=!aktualny.color;
    aktualny.left.color=!aktualny.left.color;
    aktualny.right.color=!aktualny.right.color;
    }

    /*private Node rotateL(Node aktualny)
    { Node key=aktualny.right;
      aktualny.right=key.left;
      key.left=aktualny;
      key.color=aktualny.color;
      aktualny.color=RED;
      return key; }*/

    private Node rotateL(Node aktualny) {
        assert (aktualny != null) && isRed(aktualny.right);
        Node x = aktualny.right;
        aktualny.right = x.left;
        x.left = aktualny;
        x.color = x.left.color;
        x.left.color = RED;
        return x;
    }
    private Node rotateR(Node aktualny) {
        assert (aktualny != null) && isRed(aktualny.right);
        Node x = aktualny.left;
        aktualny.left = x.right;
        x.right = aktualny;
        x.color = x.right.color;
        x.right.color = RED;
        return x;
    }
      /*private Node rotateR(Node aktualny)
    { Node key=aktualny.left;
      aktualny.left=key.right;
      key.right=aktualny;
      key.color=aktualny.color;
      aktualny.color=RED;
      return key; }*/


    public Node findNode(Key key){
		Node aktualny = root;
		int comp = 0;
		while (aktualny != null && (comp = key.compareTo(aktualny.key))!=0)
			aktualny = comp<0 ? aktualny.left : aktualny.right;
		return aktualny;
	}

    public void printInOrder(Node aktualny)
	{   //od najmniejszego do najwiekszego
		if(aktualny.left!=null)
			printInOrder(aktualny.left);
		System.out.println(aktualny);
		if(aktualny.right!=null)
			printInOrder(aktualny.right);
	}
	public void printPostOrder(Node aktualny)
	{   //parent comes last
		if(aktualny.left!=null)
			printPostOrder(aktualny.left);
		if(aktualny.right!=null)
			printPostOrder(aktualny.right);
		System.out.println(aktualny);
	}
	public void printPreOrder(Node aktualny)
	{
		if(aktualny != null){
			System.out.println(aktualny);
			printPreOrder(aktualny.left);
			printPreOrder(aktualny.right);
		}
	}
	public int height(Node aktualny){

		if(aktualny == null){
			return 0;
		}else{
			//jako ze to nie koniec to dodajemy jeden do obecnie obliczonej juz wysokosci,
			//wieksza z głebokosci, bo poddrzewo lew i prawe mogą byc roznej wiekosci
			return 1 + Math.max(height(aktualny.left), height(aktualny.right));
		}
	}





    private class Node {

    	Key key;           // key
        Node left;
        Node right;  // links to left and right subtrees
        boolean color;     // color of parent link
        int N;             // subtree count

        public Node(Key key) {
	          this.key = key;
	          left = right = null;
	          color = RED;
        }

    }

}