从源码解析TreeMap

     上篇文章我们介绍了HashMap集合，这是一个键值对集合，可以高效的按照键查找数值。但是它有一个缺陷：数据如果是无序的可以是很高效的，但是如果数据需要排列有顺序就不适合了。本篇将要介绍的一个集合是树集键值对（TreeMap），它能够对数据按照键值有序的存储。
     在介绍TreeMap之前，我们来了解一种数据结构：排序二叉树。相信学过数据结构的同学知道，这种结构的数据存储形式在查找的时候效率非常高。

这里写图片描述

第三种情况，找到待删结点的后继结点将后继结点替换到待删结点并删除后继结点（将问题转换为删除后继结点，通过前面两种可以解决）

这里写图片描述

删除后继结点

这里写图片描述
下面我们看代码：

/*代码虽多，我们一点一点看*/
    private void deleteEntry(Entry<K,V> p) {
        modCount++;
        size--;

        // If strictly internal, copy successor's element to p and then make p
        // point to successor.
        if (p.left != null && p.right != null) {
            Entry<K,V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children

        // Start fixup at replacement node, if it exists.
        Entry<K,V> replacement = (p.left != null ? p.left : p.right);

        if (replacement != null) {
            // Link replacement to parent
            replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left  = replacement;
            else
                p.parent.right = replacement;

            // Null out links so they are OK to use by fixAfterDeletion.
            p.left = p.right = p.parent = null;

            // Fix replacement
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
        } else if (p.parent == null) { // return if we are the only node.
            root = null;
        } else { //  No children. Use self as phantom replacement and unlink.
            if (p.color == BLACK)
                fixAfterDeletion(p);

            if (p.parent != null) {
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                p.parent = null;
            }
        }
    }

     首先，判断待删结点是否具有两个孩子，如果有调用函数 successor返回后继结点，并且替换待删结点。对于这条语句：Entry>K,V< replacement = (p.left != null ? p.left : p.right); ，我们上述的三种情况下replacement的取值值得研究，如果是第一种情况（叶子结点），那么replacement取值为null，进入下面的判断，第一个if过，第二个判断待删结点是否是根结点（只有根结点的父结点为null），如果是说明整个树只有一个结点，那么直接删除即可，如果不是根结点就说明是叶子结点，此时将父结点赋值为null然后删除即可。
对于第二种情况下（只有一个孩子结点时候），最上面的if语句是不做的，如果那一个结点是左孩子 replacement为该结点，然后将此结点跳过父结点挂在待删结点的下面，如果那一个孩子是右孩子，replacement为该结点，同样操作。
第三种情况（待删结点具有两个孩子结点），那肯定执行最最上面的if语句中代码，找到后继结点替换待删结点（后继结点一定没有左孩子），成功的将问题转换为删除后继结点，又因为后继结点一定没有左孩子，整个问题已经被转换成上述两种情况了，（假如后继结点没有右孩子就是第一种，假如有就是第二种）所以replacement = p.right，下面分情况处理。删除方法结束。
     小结一下，删除结点难点在于删除指定键值的结点，主要分为三种情况，叶子结点，一个孩子结点，两个孩子结点。而对于不同的情况，jdk编写者将最难的两个孩子结点转换为前两种较为简单的方式，可见大神之作。钦佩。
     最后还是要说，本篇文章为博主反复研究jdk源码总结而来，如果有错误，望指出。