package practice;

public class TestMain {
    public static void main(String[] args) {
        int[] ao = {5, 1, 18, 3, 8, 20, 13, 16, 12};
        Integer[] a = new Integer[9];
        for (int i = 0; i < a.length; i++) {
            a[i] = new Integer(ao[i]);
        }
        RedBlackBST<Integer,String> tree= new RedBlackBST<Integer,String>();
        for (int i = 0; i < a.length; i++) {
            tree.put(a[i], a[i].toString());
        }
        
        tree.print();
    }
}
/*
 * 红黑树
 * 与2-3树比较，红链接即表示像2-3树中的3-节点4-节点一样在"同一位置"（将红链接画平）
 */
class RedBlackBST <K extends Comparable<K>, V> {
    private static final boolean RED   = true;
    private static final boolean BLACK = false;

    private Node root;
    
    private class Node{
        K key;
        V value;
        Node left, right;
        int N;
        boolean color;
        
        public Node(K key, V value, int N, boolean color) {
            this.key   = key;
            this.value =http://www.mamicode.com/ value;
            this.N     = N;
            this.color = color;
        }
    }
    /*
     * 插入节点
     */
    public void put(K key, V value) {
        root = put(root, key, value);
    }
    private Node put(Node node, K key, V value) {
        if (node == null) { return new Node(key, value, 1, RED);}
        /*
         * 前面部分与二叉树插入一致，红黑树就是像二叉树一样插入后进行调整（旋转，颜色转换）
         */
        if (compare(key, node.key) < 0)      { node.left = put(node.left, key, value);} 
        else if (compare(key, node.key) > 0) { node.right = put(node.right, key, value);}
        else                                 { node.value =http://www.mamicode.com/ value;}
        /*
         * 这里的旋转就是为了保证"同一位置"（即一个节点有两条红链接）的三个节点由从小到大排序且中间的节点连着他们的父节点
         * 颜色转换即是2-3树中的"向上增长"
         */
        if (!isRed(node.left)&&isRed(node.right))    { node = rorateLeft(node);} //左旋
        if (isRed(node.left)&&isRed(node.left.left)) { node = rorateRight(node);} //右旋
        if (isRed(node.left)&&isRed(node.right))     { flipColors(node);} //颜色转换
        
        node.N = size(node.left) + size(node.right) + 1;
        return node;
    }
    /*
     * 节点左旋 父节点为dad 红节点为son（dad为动图中的E son为图中的S）
     * 当右子节点是红色而左子节点是黑色，就以本节点为dad，右子节点为son进行左旋
     */
    private Node rorateLeft(Node dad) {
        Node son = dad.right;
        dad.right = son.left;
        son.left = dad;
        son.color = dad.color;
        dad.color = RED;
        son.N = dad.N;
        dad.N = size(dad.left) + size(dad.right) +1;
        return son;
    }
    /*
     * 节点右旋 父节点为dad 红节点为son
     * 当左子节点是红色且它的左子节点也是红色，就以本节点为dad，左子节点为son进行右旋
     */
    private Node rorateRight(Node dad) {
        Node son = dad.left;
        dad.left = son.right;
        son.right = dad;
        son.color = dad.color;
        dad.color = RED;
        son.N = dad.N;
        dad.N = size(dad.left) + size(dad.right) +1;
        return son;
    }
    /*
     * 颜色转换
     * 如果这个节点的左右子节点都为红色，就把他们都变为黑色，然后把自己变成红色
     */
    private void flipColors(Node node) {
        node.color = RED;
        node.left.color = BLACK;
        node.right.color =BLACK;
    }
    /*
     * 是否为红
     */
    private boolean isRed(Node node) {
        if (node == null) { return false;}
        return node.color == RED;
    }
    /*
     * 树的大小
     */
    private int size(Node node) {
        if (node == null) { return 0;}
        else              { return node.N;}
    }
    /*
     * key1 <  key2 -1
     * key1 >  key2  1
     * key1 == key2  0
     */
    private int compare(K key1, K key2) {
        return key1.compareTo(key2); 
    }
    public void print() {
        print(root);
    }
    private void print(Node node) {
        if (node == null) {
            return;
        }
        print(node.left);
        System.out.println("key = "+node.key+" node.N = "+node.N);
        print(node.right);
    }

}