Java集合之TreeMap源码解析中篇

前言

上期我介绍了TreeMap的基本结构以及put方法的解读，包括自平衡保持红黑树特性的种种变化，

本期主要是承接上期Java集合之TreeMap源码解析上篇（←戳）的内容，继续深入探讨。

 

建立一个简单的红黑树

 public static void main(String[] args) {
        TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
        map.put(50,3001);
        map.put(30,3002);
        map.put(70,3003);
        map.put(20,3004);
        map.put(40,3005);
        map.put(60,3006);
        map.put(80,3007);
        map.put(85,3008);
}

第2行，新增一个结点50，

由于root为null，因此50便成为树结构的根，颜色为黑色，如下图所示，

第3行，新增一个结点30，找到30的父结点为50，新增之后如下图所示

符合红黑树的5条规则，因此无须调整，

第4行，新增一个结点70，找到70的父结点为50，新增之后如下图所示

依然符合红黑树的5条规则，因此无须调整，

第5行，新增一个结点20，找到20的父结点为30，新增之后如下图所示，

违反了红黑树的规则，红色结点的两个子节点都是黑色。因此我们需要fixAfterInsertion(20)，此处我把元素20标记为x

由于x不为空，且不是根结点，同时满足x的父结点30位红色，我们进入调整的动作，

由于20的父结点30是20父结点的父结点 的左结点，所以我们取到20的父结点的父结点的右结点70，标记为y，

因为y是红色，所以我们把x的父结点变为黑色，y变为黑色，同时把根节点变为红色，同时把x的引用指向x的父结点的父结点，也就是50，

由于50是根，结束调整，最后将50变为黑色，如下图所示

第7行，新增元素40，找到40的父结点30，新增之后如下图所示，

符合红黑树的5条规则，因此不需要调整。

第8-9行新增元素60,80，皆没有破坏红黑树，都不需要调整，如下图所示，

第10行，新增元素85，找到85的父结点为80，新增之后如下图所示，

违反了红黑树的规则，红色结点的两个子节点必须为黑色，因此我们需要fixAfterInsertion(85)，此处我把元素85标记为x

 

夜有点深了，85如何？且听下回分解。