通过分析 JDK 源代码研究 TreeMap 红黑树算法实现

核心提示： 对排序二叉树，若按中序遍历就可以得到由小到大的有序序列，通过分析 JDK 源代码研究 TreeMap 红黑树算法实现(4)，如图 1 所示二叉树，中序遍历得：{2，新的value覆盖原有的value，//并返回原有的valueelsereturnt.setValue(value);}while(

对排序二叉树，若按中序遍历就可以得到由小到大的有序序列。如图 1 所示二叉树，中序遍历得：

{2，3，4，8，9，9，10，13，15，18}

创建排序二叉树的步骤，也就是不断地向排序二叉树添加节点的过程，向排序二叉树添加节点的步骤如下：

以根节点当前节点开始搜索。

拿新节点的值和当前节点的值比较。

如果新节点的值更大，则以当前节点的右子节点作为新的当前节点；如果新节点的值更小，则以当前节点的左子节点作为新的当前节点。

重复 2、3 两个步骤，直到搜索到合适的叶子节点为止。

将新节点添加为第 4 步找到的叶子节点的子节点；如果新节点更大，则添加为右子节点；否则添加为左子节点。

掌握上面理论之后，下面我们来分析 TreeMap 添加节点（TreeMap 中使用 Entry 内部类代表节点）的实现，TreeMap 集合的 put(K key, V value) 方法实现了将 Entry 放入排序二叉树中，下面是该方法的源代码：

　public　V　put(K　key,　V　value)　
　{　
　　//　先以　t　保存链表的　root　节点　
　　Entry<K,V>　t　=　root;　
　　//　如果　t==null，表明是一个空链表，即该　TreeMap　里没有任何　Entry　
　　if　(t　==　null)　
　　{　
　　　　//　将新的　key-value　创建一个　Entry，并将该　Entry　作为　root　
　　　　root　=　new　Entry<K,V>(key,　value,　null);　
　　　　//　设置该　Map　集合的　size　为　1，代表包含一个　Entry　
　　　　size　=　1;　
　　　　//　记录修改次数为　1　
　　　　modCount++;　
　　　　return　null;　
　　}　
　　int　cmp;　
　　Entry<K,V>　parent;　
　　Comparator<?　super　K>　cpr　=　comparator;　
　　//　如果比较器　cpr　不为　null，即表明采用定制排序　
　　if　(cpr　!=　null)　
　　{　
　　　　do　{　
　　　　　　//　使用　parent　上次循环后的　t　所引用的　Entry　
　　　　　　parent　=　t;　
　　　　　　//　拿新插入　key　和　t　的　key　进行比较　
　　　　　　cmp　=　cpr.compare(key,　t.key);　
　　　　　　//　如果新插入的　key　小于　t　的　key，t　等于　t　的左边节点　
　　　　　　if　(cmp　<　0)　
　　　　　　　　t　=　t.left;　
　　　　　　//　如果新插入的　key　大于　t　的　key，t　等于　t　的右边节点　
　　　　　　else　if　(cmp　>　0)　
　　　　　　　　t　=　t.right;　
　　　　　　//　如果两个　key　相等，新的　value　覆盖原有的　value，　
　　　　　　//　并返回原有的　value　
　　　　　　else　
　　　　　　　　return　t.setValue(value);　
　　　　}　while　(t　!=　null);　
　　}　
　　else　
　　{　
　　　　if　(key　==　null)　
　　　　　　throw　new　NullPointerException();　
　　　　Comparable<?　super　K>　k　=　(Comparable<?　super　K>)　key;　
　　　　do　{　
　　　　　　//　使用　parent　上次循环后的　t　所引用的　Entry　
　　　　　　parent　=　t;　
　　　　　　//　拿新插入　key　和　t　的　key　进行比较　
　　　　　　cmp　=　k.compareTo(t.key);　
　　　　　　//　如果新插入的　key　小于　t　的　key，t　等于　t　的左边节点　
　　　　　　if　(cmp　<　0)　
　　　　　　　　t　=　t.left;　
　　　　　　//　如果新插入的　key　大于　t　的　key，t　等于　t　的右边节点　
　　　　　　else　if　(cmp　>　0)　
　　　　　　　　t　=　t.right;　
　　　　　　//　如果两个　key　相等，新的　value　覆盖原有的　value，　
　　　　　　//　并返回原有的　value　
　　　　　　else　
　　　　　　　　return　t.setValue(value);　
　　　　}　while　(t　!=　null);　
　　}　
　　//　将新插入的节点作为　parent　节点的子节点　
　　Entry<K,V>　e　=　new　Entry<K,V>(key,　value,　parent);　
　　//　如果新插入　key　小于　parent　的　key，则　e　作为　parent　的左子节点　
　　if　(cmp　<　0)　
　　　　parent.left　=　e;　
　　//　如果新插入　key　小于　parent　的　key，则　e　作为　parent　的右子节点　
　　else　
　　　　parent.right　=　e;　
　　//　修复红黑树　
　　fixAfterInsertion(e);　　　　　　　　　　　　　　　　//　①　
　　size++;　
　　modCount++;　
　　return　null;　
　}