2-3树 二叉树插入递归实现（红黑树）

使用和二叉查找树相同的方式插入一个结点，如果不满足红黑树性质需要修复

分析一下怎么可以递归往红黑树添加新结点

1. 怎么往普通二叉查找树添加新结点(递归实现)

假设当前结点为p

1. 递归出口
   1 、h == null 也就是p下个结点是空的（p下个结点就是需要插入的地方）,
   每一次插入都是只执行一次（叶子节点 ）
   2 、return h 每个节点执行一次
   规模也是每次-1、 层次每次+1并且越来越往外层
2. 区分往左还是往右添加
   比较带插入值和p的值，比p值大往右，小往左
3. 返回值
   开始递归返回的规模比较大， 到最后一次遍历返回的是整个树结构
   比如下面这个树
   带插入的是 0
   然后规模开始就是4 层次是1（从里到外）
   0是h == null返回 执行一次 规模-1
   124结点是 return h 执行3次 没执行一次规模-1

    /**
     *               4                 
     *              / \
     *             2   7
     *            / \   \
     *           1  3    8
     *          /
     *         0          
     */

public class RedBlackBST<Key extends Comparable<Key>, Value>{
    public Node root;
    private static final boolean RED = true;
    private static final boolean BLACK = false;
    public class Node {
        Key key;
        Value val;
        Node left, right;
        int N;
        boolean color;
        
        Node(Key key, Value val, int N, boolean color){
            this.key = key;
            this.val = val;
            this.N = N;
            this.color = color;
        }
    }
    private boolean isRed(Node x){
        if(x == null){
            return false;
        }
        return x.color == RED;
    }
    private int size(Node x){
        if(x == null){
            return 0;
        }else{
            return x.N;
        }
    }
    private Node rotateLeft(Node h){
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        x.N = h.N;
        h.N = 1+size(h.left) +size(h.right);
        return x;
    }
    
    private Node rotateRight(Node h){
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        x.N = h.N;
        h.N = 1+size(h.right) +size(h.left);
        return x;
    }
    
    private void flipColor(Node h){
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }
    
    public void put(Key key, Value val){
        root = put(root, key, val);
        root.color = BLACK;
    }
    public Node put (Node h, Key key, Value val){
        if(h == null){
            return new Node(key, val, 1, RED);
        }
        int cmp = key.compareTo(h.key);
        
        if(cmp < 0){
            //待插入值小于当前的key
            h.left = put(h.left, key, val);
        }
        else if(cmp > 0){
            //待插入值大于当前的key
            h.right = put(h.right, key, val);
        }
        else{
            //相等  直接替换  不插入元素
            h.val = val;
        }
        
        if(isRed(h.right) && !isRed(h.left)){
            h = rotateLeft(h);
            System.out.println("左旋");
        }
        if(!isRed(h.left) && isRed(h.left.left)){
            h = rotateRight(h);
            System.out.println("右旋");
        }
        if(isRed(h.right) && isRed(h.left)){
            flipColor(h);
        }
        h.N = size(h.left) + size(h.right) + 1;
        
        return h;
    }
    
}