红黑树

public class RBTree<K extends Comparable<K>, V> {
    public static boolean RED = true;
    public static boolean BLACK = false;
    public Node root;

    class Node {
        K key;
        V val;
        Node left, right;
        boolean color;
        int size;//高度

        Node(K key, V val, boolean color, int size) {
            this.key = key;
            this.val = val;
            this.color = color;
            this.size = size;
        }

        public String toString() {
            return "（K:" + key + " V:" + val + " 色:" + (color==true?"红":"黑") + " s:" + size+ " 左:" + left + " 右:" + right +"）";
        }
    }

    public RBTree() {
    }

    public boolean isRed(Node x) {
        if (null == x)
            return false;//null是黑色
        return x.color == RED;
    }

    public int size(Node x) {
        if (x == null)
            return 0;
        return x.size;
    }

    public int size() {
        return size(root);
    }

    public boolean isEmpty() {
        return root == null;
    }

    public V get(K key) {
        if (key == null)
            throw new IllegalArgumentException();
        return get(root, key);
    }

    public V get(Node n, K key) {
        while (n != null) {
            if (key.compareTo(n.key) == 0)
                return n.val;
            else if (key.compareTo(n.key) < 0)
                n = n.left;
            else
                n = n.right;
        }
        return null;
    }

    private Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;//节点重挂
        x.left = h;//旋转
        x.color = x.left.color;
        x.left.color = RED;
        x.size = h.size;
        h.size = size(h.left) + size(h.right) + 1;
        return x;
    }

    private Node rotateRight(Node h) {//h.left和h.left.left是红色就右旋转h，
        Node x = h.left;
        h.left = x.right;//节点重挂
        x.right = h;//旋转
        x.color = x.right.color;
        x.right.color = RED;
        x.size = h.size;
        h.size = size(h.left) + size(h.right) + 1;
        return x;
    }

    private void flipColors(Node h) {// 颜色翻转
        h.color = !h.color;
        h.left.color = !h.left.color;
        h.right.color = !h.right.color;
    }

    public void put(K key, V val) throws Exception {
        if (key == null || val == null)
            throw new Exception();
        root = put(root, key, val);
        root.color = BLACK;
    }
    
    //红黑树调整是从下到上，比较路上的所有节点，依次调整，不在比较路上的节点不用调整，调整时候看的也只是左右2个子节点。
    private Node put(Node h, K key, V val) {//递归看形参，进去时候依次是5.0 4.0 3.0 2.0 1.0，出来时候是反过来的，依次是1.0搞完然后2.0搞完然后3.0搞完然后4.0然后5.0。
        if (h == null)
            return new Node(key, val, RED, 1);
        int cmp = key.compareTo(h.key);// key < h.key
        if (cmp < 0) {
            // 放到h的左边，返回新的h的左边，因为有可能会翻转什么的，所以返回新的左节点。
            h.left = put(h.left, key, val);
        } else if (cmp > 0) {
            // 放到h的右边，返回新的h的右边，
            h.right = put(h.right, key, val);
        } else {
            h.val = val;
        }
        //每次给h增加左节点或者右节点之后，都要调整节点h。递归从下到上依次调整。
        if (isRed(h.right) && !isRed(h.left))// h的右节点红色，左节点是null或者黑色。节点的右边不能是红色（性质）。
            h = rotateLeft(h);
        if (isRed(h.left) && isRed(h.left.left))
            h = rotateRight(h);
        if (isRed(h.left) && isRed(h.right))
            flipColors(h);

        h.size = size(h.left) + size(h.right) + 1;
        return h;
    }

    public int getHeight() {
        return getHeight(root);
    }

    private int getHeight(Node p) {// 递归：一个函数里面依赖包含另一个函数。
        if (p == null)
            return 0;
        return Math.max(getHeight(p.left), getHeight(p.right)) + 1;
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws Exception {
        RBTree rb = new RBTree();
        rb.put(5.0, 5.00);
        rb.put(4.0, 4.00);
        rb.put(3.0, 3.00);
        rb.put(3.5, 3.50);
        rb.put(2.9, 2.90);
        rb.put(3.6, 3.60);
        rb.put(3.55, 3.550);
    }
}