上一篇文章介绍了红黑树的5个特性以及红黑树的修复方案，这一篇文章从图解的角度来详细介绍红黑树。

着重说明：红黑树是特殊的二叉查找树，也成为二叉排序树，二叉查找树有以下几个特点：

特点1：若左子树不为空，则左子树的所有节点的值都小于它的根节点的值特点2：若右子树不为空，则右子树的所有节点的值都大于它的根节点的值特点3：左子树和右子树都是二叉查找树。

例如：9,3,5,7,2,4,6,1,8依次添加到红黑树

第一步：9添加到红黑树中，默认颜色为红色，此时符合情景1。此情景违反了红黑树的特性2：根节点一定为黑色节点，修复方案如下：

第二步：3添加到红黑树中，默认为红色，根据二叉查找树的特性3<9，所以3是9的左子树，此时符合情景2，不需要修复

第三步：5添加到红黑树中，默认为红色，根据二叉查找树的特性：5<9,应该向左子树查找，3<5,所有5是3的右子树。添加3后，树变成了如下图示：

从图示可以得知新插入的节点5的父节点为红色，叔叔节点为空，此时符合情景4，根据二叉查找树的特性，我们的解决方案如下：

1：进行左旋：以5节点为中心，3节点逆时针旋转2：进行右旋：已9节点为中心，5节点顺时针旋转

第四步：7添加到红黑树中，默认为红色，根据二叉查找树的特性，7>5,所以向5节点右子树查找，7<9，所以7节点应该是9的左子树。添加7后，树变成了图示：

从上图可以得知新插入的节点7的父节点为红色，叔叔节点存在且为红色，此时符合情景3，解决方案如下：

1：将3节点和9节点的颜色从红色变成黑色2：按照情景3，应该将5节点变成红色，但是5节点为根节点，所有5不在变色

第五步：2添加到红黑树中，默认为红色，根据二叉查找树的特性，2<5,所以向5节点左子树查找，2<3，所以2是3的左子树。图示如下：

如上图所示，此时的树完全符合红黑树的5个特征，所以不需要修复

第六步：4添加到红黑树中，默认为红色，根据二叉查找树的特性，4<5,所以向5节点左子树查找，3<4，所以4是3的右子树，图示如下：

如上图所示，此时的树也完全符合红黑树的5个特征，所以不需要修复

第七步：1添加到红黑树中，默认为红色，根据二叉查找树的特性，8>5，所以向5节点右子树查找，8<9，所以向9的左子树查找，8>7，所以8是7的右子树，图示如下：

从上图可以得知，新插入节点8后，违反了红黑树的特性4，符合情景4，修复方案如下：

1：进行左旋，以8为中心，7逆时针旋转2：进行右旋，已9为中心，7顺时针旋转

通过不断的修复，最终的红黑树如下：

通过上面的一个实例，不知道大家是否理解了红黑树，通过对红黑树节点的添加和删除，会破坏红黑树的特性，通过对树的变色和旋转对红黑树进行修复。下面对修复红黑树的方法在进行一次详细的总结。

第一种情况：插入新节点x前为空树

解决方案：x.red=true

第二种情况：插入新节点x的父节点为黑色节点，图示如下：

节点N代表不存在或者子红黑树

解决方案：这种情况没有违反红黑树的特性，所以不需要修复

第三种情况：如图所示,父节点和叔叔节点都存在，且颜色都为红色

解决方案：1：xp.red=false,u.red=false,xpp.red=true2:以x=xpp，xpp作为目标节点，继续验证

第四种情况：如图所示：

u标示不存在或者为黑色节点或者为子树

解决方案：1:xp.red=false,xpp.red=true2:xpp进行右旋

第五种情况：如图所示

u标示不存在或者为黑色节点或者为子树

解决方案：1:x进行右旋，变成xpp-->x-->xp2:x.red=false,xpp.red=true3:xpp进行左旋

第六种情况：如图所示

解决方案：1:x进行左旋，变成xpp-->x-->xp2:x.red=false,xpp.red=true3:xpp进行右旋

第七种情况：如图所示

解决方案：1:xp.red=false,xpp.red=true2:xpp进行左旋

上述七种情况包含了红黑树的所有修复情况，多多琢磨就可以理解，下一篇文章我们继续开始分析HashMap的源码。