红黑树

规则

（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

put（k,v）

0.若树为空，直接新建一个节点并设为根节点。
1.找到里k值最近的节点n，若n.k等于k则直接修改n.v。
2.判断k值大于还是小于n.k，若大于将新节点p插入到n的右边，否则左边。
3.若n是黑色节点则直接返回，否则调整红黑树使其满足红黑树规则，该调整的条件都是父节点为红色。
4.设f为p的父节点，c为f的兄弟节点（f的父节点的另一个节点），若c为红色，则将c和f都设为黑色
将f的父节点设为当前节点，并将当前节点设为红色。
5.若c为黑色，而f为其父节点的左儿子。并且n是f的右儿子，将当前节点设为f，并以当前节点为中心左旋。
6.若c为黑色，而f为其父节点的左儿子。并且n是f的左儿子，将f设为黑色，f的父节点设为红色，以f的父节点
以中心左旋。
7.若c为黑色，而f为其父节点的右儿子，5,6情况反转。
8.设置根节点为黑色。

remove（k）

1.若树为空，返回空。
2.若树只有一个根节点root，且root.k等于k，则直接删除root.
3.若未找到,返回空
4.找到该节点n
5.若n有两个儿子，则找n的后置节点，后置节点为n的左儿子的最大右子孙。
即：for(n=n.left;n.right != null;n = n.right);
6.记录n的颜色ncolor
7.若n只有一个儿子，将n删掉，用n的父节点的子节点设为n的儿子。将n的儿子设为n，若n的ncolor有一个是红色则将n设为黑色，返回。若n没有儿子，并且n为红色，直接删掉，否则完成下面的调整过程后删掉n。
8.开始调整(假设n为f的左儿子)，调整前提是n部位根节点且n为黑色
9.设b为n的兄弟节点，若b为红色则设置b为黑色，f为红色，以f为节点左旋。
10.如果b和它两个儿子都为黑色，则设b为红色，设当前节点为f。
11.如果b的右儿子为红色，则设b为红色，b的右儿子为黑色，以b为节点右旋。
12.如果b的左儿子为红色，则让b为f的颜色，f为黑色，b的左儿子为黑色，以f为节点右旋。设n为root节点，跳出调整。
13.若n为f的右儿子，11,12左右反转。
14.将n的颜色设为黑色。

实现代码

import java.util.*;

/**
 * @创建人 wanqilin
 * @创建时间 2018/10/19
 * @描述
 */
public class RBTree<K,V> {

    private TreeNode root = null;
    private Comparator<K> ck;
    private long size;

    RBTree(Comparator<K> ck){this.ck = ck;}

    RBTree(){
        ck = new Comparator<K>() {
            @Override
            public int compare(K o1, K o2) {
                return o1.hashCode() - o2.hashCode();
            }
        };
    }

    public V remove(K k){
        TreeNode n = find(k);
        if(n == null || !n.k.equals(k)){
            return null;
        }
        V v = n.v;
        TreeNode tmp = n;

        if(n.f == null){
            size --;
            root = null;
            return v;
        }


        if(n.l != null && n.r != null){
            n = n.l;
            for(;n.r != null;n = n.r);
            tmp.k = n.k;
            tmp.v = n.v;
        }

        boolean isl = n.f.l == n;
        boolean isRed = n.red;
        if(n.l != null){
            if(isl){
                n.f.l = n.l;
            }else{
                n.f.r = n.l;
            }
            n.l.f = n.f;
            n = n.l;
        }else if(n.r != null){
            if(isl){
                n.f.l = n.r;
            }else{
                n.f.r = n.r;
            }
            n.r.f = n.f;
            n = n.r;
        }else{
            if(!n.red){
                fixAfterDetele(n);
            }
            if(isl){
                n.f.l = null;
            }else{
                n.f.r = null;
            }
            size--;
            return v;
        }

        if(isRed ^ n.red){
            n.red = false;
            size --;
            return v;
        }
        TreeNode b;

        fixAfterDetele(n);

        size --;
        return v;


    }

    void fixAfterDetele(TreeNode n){
        boolean isl;
        TreeNode b;
        while (!n.red && n.f != null){
            isl = n.f.l == n;
            b = isl ? n.f.r : n.f.l;

            if(b.red){
                b.red = false;
                n.f.red = true;
                if(isl){
                    leftRotate(n.f);
                }else{
                    rightRotate(n.f);
                }
            }else{
                if((b.l == null || !b.l.red) && (b.r == null || !b.r.red)){
                    b.red = true;
                    n = n.f;
                }else if(b.l != null && b.l.red){
                    if(isl){
                        b.red = true;
                        b.l.red = false;
                        rightRotate(b);
                    }else{
                        b.red = n.f.red;
                        n.f.red = false;
                        b.l.red = false;
                        rightRotate(n.f);
                        n = root;
                    }
                }else{
                    if(isl){
                        b.red = n.f.red;
                        n.f.red = false;
                        b.r.red = false;
                        leftRotate(n.f);
                        n = root;
                    }else{
                        b.red = true;
                        b.r.red = false;
                        leftRotate(b);
                    }
                }
            }
        }
        n.red = false;
    }

    public V put(K k,V v){
        if(root == null){
            root = new TreeNode(k,v,null,null,null,false);
            size++;
            return root.v;
        }

        TreeNode n = find(k);
        if(n == null) return null;
        if(compare(n.k,k) == 0){
            n.v = v;
            return n.v;
        }

        TreeNode addition = new TreeNode(k,v,n,null,null,true);

        if(compare(n.k,k) < 0){
            n.r = addition;
        }else{
            n.l = addition;
        }

        if(!n.red){
            size++;
            return addition.v;
        }
        n = addition;
        TreeNode c ;

        while (n.f != null && n.f.red){
            boolean isl = n.f == n.f.f.l;
            c = isl ? n.f.f.r : n.f.f.l;
            if(c != null && c.red){
                c.red = false;
                n.f.red = false;
                n = n.f.f;
                n.red = true;
            }else{
                if(isl){
                    if(n == n.f.r){
                        n = n.f;
                        leftRotate(n);
                    }else{
                        n.f.red = false;
                        n.f.f.red = true;
                        rightRotate(n.f.f);
                    }
                }else{
                    if(n == n.f.l){
                        n = n.f;
                        rightRotate(n);
                    }else{
                        n.f.red = false;
                        n.f.f.red = true;
                        leftRotate(n.f.f);
                    }
                }
            }

        }
        root.red = false;
        size++;
        return addition.v;
    }

    private void rightRotate(TreeNode n) {
        TreeNode l = n.l;
        if (l == null) throw new RuntimeException();

        n.l = l.r;
        if(n.l != null) n.l.f = n;
        l.r = n;

        l.f = n.f;
        if(l.f == null){
            root = l;
        }else{
            if(l.f.r == n){
                l.f.r = l;
            }else{
                l.f.l = l;
            }
        }
        n.f = l;
    }

    private void leftRotate(TreeNode n) {
        TreeNode r = n.r;
        if(r == null) throw new RuntimeException();


        n.r = r.l;
        if(n.r != null)n.r.f = n;
        r.l = n;
        r.f = n.f;
        if(n.f == null){
            root = r;
        }else{
            if(r.f.r == n){
                r.f.r = r;
            }else{
                r.f.l = r;
            }
        }
        n.f = r;
    }

    private int compare(K k1,K k2){return ck.compare(k1,k2);}
    public TreeNode get(K k){
        TreeNode res = find(k);
        return res == null ? null : compare(res.k,k) == 0 ? res : null;
    }

    private TreeNode find(K k) {
        if(root == null) return null;

        for(TreeNode n = root;;){
            int res = ck.compare(n.k,k);
            if(res == 0) return n;
            if(res < 0 && n.r != null){
                n = n.r;
            }else if(res > 0 && n.l != null){
                n = n.l;
            }else{
                return n;
            }
        }
    }

    public boolean check(){
        if(root == null) return true;
        TreeNode n = root;
        if(root.red) return false;

        Stack<CheckEntity> stack = new Stack<>();
        stack.push(new CheckEntity(0,n));
        for (;;){
            CheckEntity check = stack.pop();
            n = check.node;
            if (n.red){
                if(n.l != null && n.l.red){
                    System.out.println("red red");
                    return false;
                }
                if(n.r != null && n.r.red){
                    System.out.println("red red");
                    return false;
                }
            }
            if(check.leftVal == -1){
                check.leftVal = 0;
                if(n.l != null){
                    if(compare(n.k,n.l.k) < 0){
                        System.out.println("l > f");
                        return false;
                    }
                    stack.push(check);
                    stack.push(new CheckEntity(-1,n.l));
                    continue;
                }
            }
            if(check.rightVal == -1){
                check.rightVal = 0;
                if(n.r != null){
                    if(compare(n.k,n.r.k) > 0){
                        System.out.println("r < f");
                        return false;
                    }
                    stack.push(check);
                    stack.push(new CheckEntity(1,n.r));
                    continue;
                }
            }
            if(check.rightVal != check.leftVal){
                System.out.println("lv != rv");
                return false;
            }

            long val = check.rightVal;
            val = n.red ? val : val + 1;

            switch (check.pos){
                case -1:
                    stack.peek().leftVal = val;
                    break;
                case 1:
                    stack.peek().rightVal = val;
                    break;
                case 0:
                    return true;
            }
        }
    }

    public static void test(){
        RBTree<Integer,Integer> tree = new RBTree<Integer,Integer>();
        Random r = new Random(1);
        int loop = 10000;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < loop; i++) {
            int ra ;
            tree.put((ra = r.nextInt()),0);
            set.add(ra);
            if(!tree.check()){
                System.out.println("false");
            }
        }
        System.out.println(tree.size == set.size());
        List<Integer> remove = new LinkedList<>(set);
        long size = tree.size;
        for (int i = 0; i < loop/50; i++) {
            int index = (int) (r.nextFloat() * remove.size());
            tree.remove(remove.get(index));
            if(tree.size != --size){
                System.out.println("size false");
            }
            remove.remove(index);
            tree.check();
        }

    }

    class CheckEntity{
        long leftVal;
        long rightVal;
        int pos;
        TreeNode node;
        public CheckEntity(int pos, TreeNode node) {
            this.leftVal = -1;
            this.rightVal = -1;
            this.pos = pos;
            this.node = node;
        }
    }

    class TreeNode{
        K k;
        V v;
        TreeNode f;
        TreeNode l;
        TreeNode r;
        boolean red ;

        TreeNode(K k, V v, TreeNode f, TreeNode l, TreeNode r, boolean red) {
            this.k = k;
            this.v = v;
            this.f = f;
            this.l = l;
            this.r = r;
            this.red = red;
        }
    }

    public static void main(String[] args) {
        test();
    }
}