插入

向仅有根节点的红黑树插入新节点

如果新键值小于老键值，直接通过红色链接增加一个节点

如果新键值大于老键值，通过红色链接插入节点会产生一条红色右链接，这时候左旋即可

向2-节点插入新节点

2-节点没有与之相连的红链接

这会在红黑树的叶子节点上插入一个新的节点，并且总是用红链接进行插入，因为不增加黑链接，红黑树依然保持黑色完美平衡

这和向仅有根节点的红黑树的插入类似

向3-节点插入新节点

根据新节点的键值，分为三种情况

  • 新键最大，通过红色右链接插入新节点，在进行一次颜色转换
  • 新键最小，通过红色左链接插入新节点，中间键值的节点上出现了2条红链接，先右旋，再进行颜色转换
  • 新键介于两者之间，通过红色右链接插入新节点，中间键值的有2条红链接，先左旋，这时候与上一种情况相同，于是再右旋，最后颜色转换
image-20210811193726035

再实际处理中，因为这三种处理的部分重合，我们将三种基本处理（左旋，右旋，颜色转换）排好顺序，根据情况判断是否进行这一步的处理（三个同级的if）

首先我们通过红链接向一个叶子节点插入新节点，使之称为新节点的父节点，再判断这个父节点的情况进行处理（注意旋转操作是以父节点为参数和接收变量调用的）

  1. 如果父节点的右子节点是红色，左子节点为黑色，那么左旋
  2. 如果父节点本身由一个红色链接指向，并且也通过红色链接指向子节点，那么右旋
  3. 如果父节点的两个链接均为红链接，那么进行颜色转换
image-20210811201934124

到这里，我们就可以写出红黑树的插入方法了

    // insert the key-value pair in the subtree rooted at h
    private Node put(Node h, Key key, Value val) { 
        if (h == null) return new Node(key, val, RED, 1);

        int cmp = key.compareTo(h.key);
        if      (cmp < 0) h.left  = put(h.left,  key, val); 
        else if (cmp > 0) h.right = put(h.right, key, val); 
        else              h.val   = val;

        // fix-up any right-leaning links
        if (isRed(h.right) && !isRed(h.left))      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 void put(Key key, Value val) {
        if (key == null) throw new IllegalArgumentException("first argument to put() is null");
        if (val == null) {
            delete(key);
            return;
        }

        root = put(root, key, val);
        root.color = BLACK;
        // assert check();
    }