TreeMap的实现是红黑树算法的实现

    红黑树 又称 红-黑二叉树，它首先是一颗二叉树，它具有二叉树所有的特性。

    同时红黑树更是一颗自平衡的排序二叉树。

    一颗基本的二叉树中的任何节点的值大于它的左子节点，且小于它的右子节点。

    按照这个基本性质使得树的检索效率大大提高。

    在生成二叉树的过程是非常容易失衡的，最坏的情况就是一边倒（只有右/左子树），这样势必会导致二叉树的检索效率大大降低（O(n)），所以为了维持二叉树的平衡，大牛们提出了各种实现的算法，如：AVL，SBT，伸展树，TREAP ，红黑树等等。

平衡二叉树

    必须具备如下特性：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。也就是说该二叉树的任何一个子节点，其左右子树的高度都相近。

红黑树

    节点是红色或者黑色的平衡二叉树，它通过颜色的约束来维持着二叉树的平衡。

    对于一棵有效的红黑树二叉树而言我们必须增加如下规则：

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

        2、根节点是黑色

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

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

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

TreeMap put()方法实现分析

    在TreeMap的put()的实现方法中主要分为两个步骤，

        第一：构建排序二叉树，

        第二：平衡二叉树。

    对于排序二叉树的创建，其添加节点的过程如下：

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

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

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

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

[Java] 纯文本查看 复制代码

[/size][/font][/color][/align][align=left][color=rgb(0, 0, 0)][font=宋体][size=12pt]public V put(K key, V value) {

    //用t表示二叉树的当前节点
    Entry<K,V> t = root;

    //t为null表示一个空树，即TreeMap中没有任何元素，直接插入
    if (t == null) {  
        //将新的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;[/size][/font][/color][/align][align=left][color=rgb(0, 0, 0)][font=宋体][size=12pt]
    /*
    * 上面已经完成了排序二叉树的的构建，将新增节点插入该树中的合适位置
    * 下面fixAfterInsertion()方法就是对这棵树进行调整、平衡，具体过程参考上面的五种情况
    */
    fixAfterInsertion(e);

    //TreeMap元素数量 + 1
    size++;

    //TreeMap容器修改次数 + 1
    modCount++;

    return null;

}[/size][/font][/color][/align][align=left][color=rgb(0, 0, 0)][font=宋体][size=12pt]

上面代码中do{}代码块是实现排序二叉树的核心算法，通过该算法我们可以确认新增节点在该树的正确位置。找到正确位置后将插入即可

TreeMap的实现是红黑树算法的实现

    红黑树 又称 红-黑二叉树，它首先是一颗二叉树，它具有二叉树所有的特性。

    同时红黑树更是一颗自平衡的排序二叉树。

    一颗基本的二叉树中的任何节点的值大于它的左子节点，且小于它的右子节点。

    按照这个基本性质使得树的检索效率大大提高。

    在生成二叉树的过程是非常容易失衡的，最坏的情况就是一边倒（只有右/左子树），这样势必会导致二叉树的检索效率大大降低（O(n)），所以为了维持二叉树的平衡，大牛们提出了各种实现的算法，如：AVL，SBT，伸展树，TREAP ，红黑树等等。

平衡二叉树

    必须具备如下特性：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。也就是说该二叉树的任何一个子节点，其左右子树的高度都相近。

红黑树

    节点是红色或者黑色的平衡二叉树，它通过颜色的约束来维持着二叉树的平衡。

    对于一棵有效的红黑树二叉树而言我们必须增加如下规则：

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

        2、根节点是黑色

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

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

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

TreeMap put()方法实现分析

    在TreeMap的put()的实现方法中主要分为两个步骤，

        第一：构建排序二叉树，

        第二：平衡二叉树。

    对于排序二叉树的创建，其添加节点的过程如下：

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

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

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

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

[Java] 纯文本查看 复制代码

[/size][/font][/color][/align][align=left][color=rgb(0, 0, 0)][font=宋体][size=12pt]public V put(K key, V value) {

    //用t表示二叉树的当前节点
    Entry<K,V> t = root;

    //t为null表示一个空树，即TreeMap中没有任何元素，直接插入
    if (t == null) {  
        //将新的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;[/size][/font][/color][/align][align=left][color=rgb(0, 0, 0)][font=宋体][size=12pt]
    /*
    * 上面已经完成了排序二叉树的的构建，将新增节点插入该树中的合适位置
    * 下面fixAfterInsertion()方法就是对这棵树进行调整、平衡，具体过程参考上面的五种情况
    */
    fixAfterInsertion(e);

    //TreeMap元素数量 + 1
    size++;

    //TreeMap容器修改次数 + 1
    modCount++;

    return null;

}[/size][/font][/color][/align][align=left][color=rgb(0, 0, 0)][font=宋体][size=12pt]

上面代码中do{}代码块是实现排序二叉树的核心算法，通过该算法我们可以确认新增节点在该树的正确位置。找到正确位置后将插入即可