Java-TreeMap原理

TreeMap基于红黑树原理实现。

文章参考自博客http://blog.****.net/zhangyuan19880606/article/details/51234420，仅供学习之用。谢谢博主分享。

一、红黑树

红黑树又称红-黑二叉树，它首先是一颗二叉树，它具有二叉树的全部特性。同时红黑树更是一颗自平衡的排序二叉树。

平衡二叉树性质：是一颗空树或者它的左右两个子树的深度之差不超过1.

红黑树有以下性质： 1 每个结点必须为红或者黑；

                                2 根节点为黑色；

                                3 叶节点（空节点）为黑色；

                                4 如果一个节点是红色，则它的两个子节点必须为黑色，也就是说，不存在一条路径上有两个相邻的节点都是红色；

                                5 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点；

如图，为一课红黑树：

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

红黑树的操作：左旋、右旋、着色

红黑树的添加方法，有以下规则：

         1、新插入的节点总是红色 。

         2、如果插入节点的父节点是黑色, 能维持性质 。

         3、如果插入节点的父节点是红色, 破坏了性质. 故插入算法就是通过重新着色或旋转, 来维持性质。（一中有介绍）

插入规则： 

        1. 若新插入的节点N没有父节点，则直接当做根节点，将颜色设置为黑色

        2.父节点为黑色：

            新节点N同样是直接插入，同时颜色为红色，由于根据规则4它会存在两个黑色的叶子节点，值为null。同时由于新增节点N为红色，所以通过它的子节点的路径依然会保存着相同的黑色节点数，同样满足规则5.

        3.父节点P和其兄弟节点U均为红色：

            

            若直接插入N会出现不平衡现象。这时，需将P、U节点变黑、G节点变红。这时由于经过节点P、U的路径都必须经过G所以在这些路径上面的黑节点数目还是相同的。但是经过上面的处理，可能G节点的父节点也是红色，这个时候我们需要将G节点当做新增节点递归处理。

        4.父节点P为红色，P的兄弟节点U为黑色或者空，且新节点N为P的右孩子：

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

     

        5. 父节点P为红色，P的兄弟节点U为黑色或者空，且新节点N为P的左孩子：

            这种情况有可能是由于情况四而产生的，也有可能不是。对于这种情况先以P节点为中心进行右旋转，在旋转后产生的树中，节点P是节点N、G的父节点。但是这棵树并不规范，它违反了规则4，所以我们将P、G节点的颜色进行交换，使之其满足规范。开始时所有的路径都需要经过G其他们的黑色节点数一样，但是现在所有的路径改为经过P，且P为整棵树的唯一黑色节点，所以调整后的树同样满足规范5。

二、TreeMap

定义：

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap的put()方法：参照红黑树的添加方法（五种规则）

首先构建一棵排序二叉树（根节点值大于左孩子，小于右孩子），之后调整为平衡二叉树，依据红黑树的操作方法与规则。

自己也在学习中，再次感谢博主zhangyuan19880606的分享！