若新插入的节点N没有父节点，则直接当做依据节点插入就可以，同一时候将颜色设置为黑色。

（如图一（1））

       二、父节点为黑色

       这样的情况新节点N相同是直接插入，同一时候颜色为红色。因为依据规则四它会存在两个黑色的叶子节点。值为null。

同一时候因为新增节点N为红色。所以通过它的子节点的路径依旧会保存着相同的黑色节点数。相同满足规则5。

（如图一（2））

（图一）

       三、若父节点P和P的兄弟节点U都为红色

       对于这样的情况若直接插入肯定会出现不平衡现象。怎么处理？P、U节点变黑、G节点变红。这时因为经过节点P、U的路径都必须经过G所以在这些路径上面的黑节点数目还是相同的。

可是经过上面的处理，可能G节点的父节点也是红色。这个时候我们须要将G节点当做新增节点递归处理。

       四、若父节点P为红色。叔父节点U为黑色或者缺少，且新增节点N为P节点的右孩子

       对于这样的情况我们对新增节点N、P进行一次左旋转。这里所产生的结果事实上并没有完毕。还不是平衡的（违反了规则四），这是我们须要进行情况5的操作。

       五、父节点P为红色，叔父节点U为黑色或者缺少，新增节点N为父节点P左孩子

       这样的情况有可能是因为情况四而产生的，也有可能不是。对于这样的情况先已P节点为中心进行右旋转。在旋转后产生的树中，节点P是节点N、G的父节点。可是这棵树并不规范。它违反了规则4，所以我们将P、G节点的颜色进行交换。使之其满足规范。

開始时全部的路径都须要经过G其它们的黑色节点数一样。可是如今全部的路径改为经过P，且P为整棵树的唯一黑色节点，所以调整后的树相同满足规范5。

       上面展示了红黑树新增节点的五种情况。这五种情况涵盖了全部的新增可能。无论这棵红黑树多么复杂，都能够依据这五种情况来进行生成。以下就来分析Java中的TreeMap是怎样来实现红黑树的。

       TreeMap put()方法实现分析

       在TreeMap的put()的实现方法中主要分为两个步骤，第一：构建排序二叉树，第二：平衡二叉树。

       1、以根节点为初始节点进行检索。

       2、与当前节点进行比对，若新增节点值较大。则以当前节点的右子节点作为新的当前节点。否则以当前节点的左子节点作为新的当前节点。

       3、循环递归2步骤知道检索出合适的叶子节点为止。

       4、将新增节点与3步骤中找到的节点进行比对。假设新增节点较大，则加入为右子节点；否则加入为左子节点。

       依照这个步骤我们就能够将一个新增节点加入到排序二叉树中合适的位置。例如以下：

public V put(K key, V value) {
           //用t表示二叉树的当前节点
            Entry<K,V> t = root;
            //t为null表示一个空树。即TreeMap中没有不论什么元素。直接插入
            if (t == null) {
                //比較key值。个人觉得这句代码没有不论什么意义，空树还须要比較、排序？
                compare(key, key); // type (and possibly null) check
                //将新的key-value键值对创建为一个Entry节点，并将该节点赋予给root
                root = new Entry<>(key, value, null);
                //容器的size = 1，表示TreeMap集合中存在一个元素
                size = 1;
                //改动次数 + 1
                modCount++;
                return null;
            }
            int cmp;     //cmp表示key排序的返回结果
            Entry<K,V> parent;   //父节点
            // split comparator and comparable paths
            Comparator<?
 super K> cpr = comparator;    //指定的排序算法
            //假设cpr不为空，则採用既定的排序算法进行创建TreeMap集合
            if (cpr != null) {
                do {
                    parent = t;      //parent指向上次循环后的t
                    //比較新增节点的key和当前节点key的大小
                    cmp = cpr.compare(key, t.key);
                    //cmp返回值小于0。表示新增节点的key小于当前节点的key。则以当前节点的左子节点作为新的当前节点
                    if (cmp < 0)
                        t = t.left;
                    //cmp返回值大于0，表示新增节点的key大于当前节点的key。则以当前节点的右子节点作为新的当前节点
                    else if (cmp > 0)
                        t = t.right;
                    //cmp返回值等于0，表示两个key值相等，则新值覆盖旧值。并返回新值
                    else
                        return t.setValue(value);
                } while (t != null);
            }
            //假设cpr为空，则採用默认的排序算法进行创建TreeMap集合
            else {
                if (key == null)     //key值为空抛出异常
                    throw new NullPointerException();
                /* 以下处理过程和上面一样 */
                Comparable<?
 super K> k = (Comparable<? super K>) key;
                do {
                    parent = t;
                    cmp = k.compareTo(t.key);
                    if (cmp < 0)
                        t = t.left;
                    else if (cmp > 0)
                        t = t.right;
                    else
                        return t.setValue(value);
                } while (t != null);
            }
            //将新增节点当做parent的子节点
            Entry<K,V> e = new Entry<>(key, value, parent);
            //假设新增节点的key小于parent的key，则当做左子节点
            if (cmp < 0)
                parent.left = e;
          //假设新增节点的key大于parent的key，则当做右子节点
            else
                parent.right = e;
            /*
             *  上面已经完毕了排序二叉树的的构建，将新增节点插入该树中的合适位置
             *  以下fixAfterInsertion()方法就是对这棵树进行调整、平衡，具体过程參考上面的五种情况
             */
            fixAfterInsertion(e);
            //TreeMap元素数量 + 1
            size++;
            //TreeMap容器改动次数 + 1
            modCount++;
            return null;
        }

/**
     * 新增节点后的修复操作
     * x 表示新增节点
     */
     private void fixAfterInsertion(Entry<K,V> x) {
            x.color = RED;    //新增节点的颜色为红色

            //循环 直到 x不是根节点。且x的父节点不为红色
            while (x != null && x != root && x.parent.color == RED) {
                //假设X的父节点（P）是其父节点的父节点（G）的左节点
                if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                    //获取X的叔节点(U)
                    Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                    //假设X的叔节点（U） 为红色（情况三）
                    if (colorOf(y) == RED) {     
                        //将X的父节点（P）设置为黑色
                        setColor(parentOf(x), BLACK);
                        //将X的叔节点（U）设置为黑色
                        setColor(y, BLACK);
                        //将X的父节点的父节点（G）设置红色
                        setColor(parentOf(parentOf(x)), RED);
                        x = parentOf(parentOf(x));
                    }
                    //假设X的叔节点（U为黑色）；这里会存在两种情况（情况四、情况五）
                    else {   
                        //假设X节点为其父节点（P）的右子树，则进行左旋转（情况四）
                        if (x == rightOf(parentOf(x))) {
                            //将X的父节点作为X
                            x = parentOf(x);
                            //右旋转
                            rotateLeft(x);
                        }
                        //（情况五）
                        //将X的父节点（P）设置为黑色
                        setColor(parentOf(x), BLACK);
                        //将X的父节点的父节点（G）设置红色
                        setColor(parentOf(parentOf(x)), RED);
                        //以X的父节点的父节点（G）为中心右旋转
                        rotateRight(parentOf(parentOf(x)));
                    }
                }
                //假设X的父节点（P）是其父节点的父节点（G）的右节点
                else {
                    //获取X的叔节点（U）
                    Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                  //假设X的叔节点（U） 为红色（情况三）
                    if (colorOf(y) == RED) {
                        //将X的父节点（P）设置为黑色
                        setColor(parentOf(x), BLACK);
                        //将X的叔节点（U）设置为黑色
                        setColor(y, BLACK);
                        //将X的父节点的父节点（G）设置红色
                        setColor(parentOf(parentOf(x)), RED);
                        x = parentOf(parentOf(x));
                    }
                  //假设X的叔节点（U为黑色）；这里会存在两种情况（情况四、情况五）
                    else {
                        //假设X节点为其父节点（P）的右子树。则进行左旋转（情况四）
                        if (x == leftOf(parentOf(x))) {
                            //将X的父节点作为X
                            x = parentOf(x);
                           //右旋转
                            rotateRight(x);
                        }
                        //（情况五）
                        //将X的父节点（P）设置为黑色
                        setColor(parentOf(x), BLACK);
                        //将X的父节点的父节点（G）设置红色
                        setColor(parentOf(parentOf(x)), RED);
                        //以X的父节点的父节点（G）为中心右旋转
                        rotateLeft(parentOf(parentOf(x)));
                    }
                }
            }
            //将根节点G强制设置为黑色
            root.color = BLACK;
        }

       对这段代码的研究我们发现,其处理过程全然符合红黑树新增节点的处理过程。所以在看这段代码的过程一定要对红黑树的新增节点过程有了解。在这个代码中还包括几个重要的操作。左旋(rotateLeft())、右旋（rotateRight()）、着色（setColor()）。

左旋：rotateLeft()

       所谓左旋转，就是将新增节点（N）当做其父节点（P），将其父节点P当做新增节点（N）的左子节点。即：G.left ---> N ,N.left ---> P。

       右旋：rotateRight()

       所谓右旋转即，P.right ---> G、G.parent ---> P。

private void rotateRight(Entry<K,V> p) {
        if (p != null) {
            //将L设置为P的左子树
            Entry<K,V> l = p.left;
            //将L的右子树设置为P的左子树
            p.left = l.right;
            //若L的右子树不为空。则将P设置L的右子树的父节点
            if (l.right != null) 
                l.right.parent = p;
            //将P的父节点设置为L的父节点
            l.parent = p.parent;
            //假设P的父节点为空，则将L设置根节点
            if (p.parent == null)
                root = l;
            //若P为其父节点的右子树。则将L设置为P的父节点的右子树
            else if (p.parent.right == p)
                p.parent.right = l;
            //否则将L设置为P的父节点的左子树
            else 
                p.parent.left = l;
            //将P设置为L的右子树
            l.right = p;
            //将L设置为P的父节点
            p.parent = l;
        }
    }

       左旋、右旋的示意图例如以下：

（左旋）                                         （右旋）

（图片来自：http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html）

       着色：setColor()

       着色就是改变该节点的颜色，在红黑树中。它是依靠节点的颜色来维持平衡的。

private static <K,V> void setColor(Entry<K,V> p, boolean c) {
        if (p != null)
            p.color = c;
    }

       四、TreeMap delete()方法

       红黑树删除节点

       针对于红黑树的添加节点而言，删除显得更加复杂，使原本就复杂的红黑树变得更加复杂。同一时候删除节点和添加节点一样，相同是找到删除的节点。删除之后调整红黑树。可是这里的删除节点并非直接删除，而是通过走了“弯路”通过一种捷径来删除的：找到被删除的节点D的子节点C。用C来替代D。不是直接删除D。因为D被C替代了，直接删除C就可以。所以这里就将删除父节点D的事情转变为了删除子节点C的事情。这样处理就将复杂的删除事件简单化了。

子节点C的规则是：右分支最左边，或者 左分支最右边的。

       红-黑二叉树删除节点，最大的麻烦是要保持 各分支黑色节点数目相等。 因为是删除。所以不用操心存在颜色冲突问题——插入才会引起颜色冲突。

       红黑树删除节点相同会分成几种情况，这里是依照待删除节点有几个儿子的情况来进行分类：

       1、没有儿子。即为叶结点。直接把父结点的相应儿子指针设为NULL。删除儿子结点就OK了。

       2、仅仅有一个儿子。那么把父结点的相应儿子指针指向儿子的独生子，删除儿子结点也OK了。

       3、有两个儿子。这样的情况比較复杂。但还是比較简单。上面提到过用子节点C替代取代待删除节点D，然后删除子节点C就可以。

       以下就论各种删除情况来进行图例解说，可是在解说之前请同意我再次啰嗦一句，请时刻牢记红黑树的5点规定：

       1、每一个节点都仅仅能是红色或者黑色

       2、根节点是黑色

       3、每一个叶节点（NIL节点，空节点）是黑色的。

       4、假设一个结点是红的。则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

       5、从任一节点到其每一个叶子的全部路径都包括相同数目的黑色节点。

       （注：已经讲三遍了。再不记住我就怀疑你是否适合搞IT了 O(∩_∩)O~）

       诚然，既然删除节点比較复杂，那么在这里我们就约定一下规则：

       1、以下要解说的删除节点一定是实际要删除节点的后继节点（N），如前面提到的C。

       2、以下提到的删除节点的树都是例如以下结构，该结构所选取的节点是待删除节点的右树的最左边子节点。

这里我们规定真实删除节点为N、父节点为P、兄弟节点为W兄弟节点的两个子节点为X1、X2。例如以下图（2.1）。

       如今我们就上面提到的三种情况进行分析、处理。

       情况一、无子节点（红色节点）

       这样的情况对该节点直接删除就可以。不会影响树的结构。因为该节点为叶子节点它不可能存在子节点-----如子节点为黑，则违反黑节点数原则（规定5），为红，则违反“颜色”原则（规定4）。 如上图（2.2）。

       情况二、有一个子节点

       这样的情况处理也是很简单的，用子节点替代待删除节点，然后删除子节点就可以。

如上图（2.3）

       情况三、有两个子节点

       这样的情况可能会略微有点儿复杂。

它须要找到一个替代待删除节点（N）来替代它，然后删除N就可以。

它主要分为四种情况。

       1、N的兄弟节点W为红色

       2、N的兄弟w是黑色的，且w的俩个孩子都是黑色的。

       3、N的兄弟w是黑色的。w的左孩子是红色。w的右孩子是黑色。

       4、N的兄弟w是黑色的，且w的右孩子时红色的。

       情况3.1、N的兄弟节点W为红色

       W为红色，那么其子节点X1、X2必然全部为黑色，父节点P也为黑色。处理策略是：改变W、P的颜色，然后进行一次左旋转。

这样处理就能够使得红黑性质得以继续保持。N的新兄弟new w是旋转之前w的某个孩子，为黑色。

这样处理后将情况3.1、转变为3.2、3.3、3.4中的一种。

例如以下：

       情况3.2、N的兄弟w是黑色的，且w的俩个孩子都是黑色的。

       这样的情况其父节点可红可黑，因为W为黑色，这样导致N子树相对于其兄弟W子树少一个黑色节点，这时我们能够将W置为红色。

这样，N子树与W子树黑色节点一致，保持了平衡。

例如以下

       将W由黑转变为红，这样就会导致新节点new N相对于它的兄弟节点会少一个黑色节点。

可是假设new x为红色，我们直接将new x转变为黑色。保持整棵树的平衡。

否则情况3.2 会转变为情况3.1、3.3、3.4中的一种。

       情况3.3、N的兄弟w是黑色的，w的左孩子是红色。w的右孩子是黑色。

       针对这样的情况是将节点W和其左子节点进行颜色交换，然后对W进行右旋转处理。

       此时N的新兄弟X1(new w)是一个有红色右孩子的黑结点，于是将情况3转化为情况4.

       情况3.4、N的兄弟w是黑色的，且w的右孩子时红色的。

       交换W和父节点P的颜色，同一时候对P进行左旋转操作。

这样就把左边缺失的黑色节点给补回来了。同一时候将W的右子节点X2置黑。这样左右都达到了平衡。

       总结

       个人觉得这四种情况比較难理解，首先他们都不是单一的某种情况。他们之间是能够进行互转的。相对于其它的几种情况，情况3.2比較好理解，仅仅仅仅是一个颜色的转变，通过降低右子树的一个黑色节点使之保持平衡。同一时候将不平衡点上移至N与W的父节点，然后进行下一轮迭代。情况3.1，是将W旋转将其转成情况2、3、4情况进行处理。而情况3.3通过转变后能够化成情况3.4来进行处理，从这里能够看出情况3.4应该终于结。

情况3.4、右子节点为红色节点。那么将缺失的黑色节点交由给右子节点，通过旋转达到平衡。

       通过上面的分析，我们已经初步了解了红黑树的删除节点情况，相对于添加节点而言它确实是选的较为复杂。以下我将看到在Java TreeMap中是怎样实现红黑树删除的。

       TreeMap deleteEntry()方法实现分析

       通过上面的分析我们确认删除节点的步骤是：找到一个替代子节点C来替代P，然后直接删除C。最后调整这棵红黑树。以下代码是寻找替代节点、删除替代节点。

private void deleteEntry(Entry<K,V> p) {
        modCount++;      //改动次数 +1
        size--;          //元素个数 -1

        /*
         * 被删除节点的左子树和右子树都不为空，那么就用 p节点的中序后继节点取代 p 节点
         * successor(P)方法为寻找P的替代节点。规则是右分支最左边，或者 左分支最右边的节点
         * ---------------------（1）
         */
        if (p.left != null && p.right != null) {  
            Entry<K,V> s = successor(p);
            p.key = s.key;
            p.value = http://www.mamicode.com/s.value;>

       五、写在最后