《Java集合详解系列》是我在完成夯实Java基础篇的系列博客后准备开始写的新系列。
成都创新互联公司服务项目包括旅顺口网站建设、旅顺口网站制作、旅顺口网页制作以及旅顺口网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，旅顺口网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到旅顺口省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
这些文章将整理到我在GitHub上的《Java面试指南》仓库，更多精彩内容请到我的仓库里查看
https://github.com/h3pl/Java-Tutorial
喜欢的话麻烦点下Star、fork哈
文章首发于我的个人博客：
www.how2playlife.com
什么是红黑树
首先，什么是红黑树呢？ 红黑树是一种“平衡的”二叉查找树，它是一种经典高效的算法，能够保证在最坏的情况下动态集合操作的时间为O（lgn）。红黑树每个节点包含5个域，分别为color,key,left,right和p。 color是在每个节点上增加的一个存储位表示节点的颜色，可以是RED或者BLACK。key为结点中的value值，left,right为该结点的左右孩子指针，没有的话为NIL，p是一个指针，是指向该节的父节点。如下图（来自维基百科）表示就是一颗红黑树，NIL为指向外结点的指针。（外结点视为没有key的结点）
红黑树有什么性质呢？一般称为红黑性质，有以下五点：
1）每个结点或者是红的或者是黑的；
2）根结点是黑的；
3）每个叶结点（NIL）是黑的；
4）如果一个结点是红的，则它的两个孩子都是黑的；
5）对每个结点，从该结点到其他其子孙结点的所有路径上包含相同数目的黑结点。
为了后面的分析，我们还得知道以下知识点。
（1）黑高度：从某个结点x出发（不包括该结点）到达一个叶结点的任意一条路径上，黑色结点的个数称为该结点x的黑高度。
（2）一颗有n个内结点的红黑树的高度至多为2lg(n+1)。 （内结点视为红黑树中带关键字的结点）
（3）包含n个内部节点的红黑树的高度是 O(log(n))。
定义
红黑树是特殊的二叉查找树，又名R-B树(RED-BLACK-TREE)，由于红黑树是特殊的二叉查找树，即红黑树具有了二叉查找树的特性，而且红黑树还具有以下特性：
有几点需要注意的是：
1.特性3中指定红黑树的每个叶子节点都是空节点，但是在Java实现中红黑树将使用null代表空节点，因此遍历红黑树时看不到黑色的叶子节点，反而见到的叶子节点是红色的
2.特性4保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的两倍，例如黑色高度为3的红黑树，其最短路径(路径指的是根节点到叶子节点)是2(黑节点-黑节点-黑节点)，其最长路径为4(黑节点-红节点-黑节点-红节点-黑节点)。
实践
红黑树操作
插入操作
首先红黑树在插入节点的时，我们设定插入节点的颜色为红色,如果插入的是黑色节点，必然会违背特性5，即改变了红黑树的黑高度，如下插入红色结点又存在着几种情况：
1.黑父
如图所示，这种情况不会破坏红黑树的特性，即不需要任何处理
2.红父
当其父亲为红色时又会存在以下的情况
红叔的情况，其实相对来说比较简单的，如下图所示，只需要通过修改父、叔的颜色为黑色，祖的颜色为红色，而且回去递归的检查祖节点即可
黑叔的情况有如下几种，这几种情况下是不能够通过修改颜色达到平衡的效果，因此会通过旋转的操作，红黑树种有两种旋转操作，左旋和右旋(现在存在的疑问，什么时候使用到左旋，什么时候使用到右旋)
- Case 1:[先右旋，在改变颜色(根节点必须为黑色，其两个子节点为红色，叔节点不用改变)],如下图所示，注意省略黑哨兵节点
- Case 2:[先左旋变成Case1中的情况，再右旋，最后改变颜色(根节点必须为黑色，其两个子节点为红色，叔节点不用改变)],如下图所示，注意省略黑哨兵节点
- Case 3:[先左旋，最后改变颜色(根节点必须为黑色，其两个子节点为红色，叔节点不用改变)],如下图所示，注意省略黑哨兵节点
- Case 4:[先右旋变成Case 3的情况，再左旋，最后改变颜色(根节点必须为黑色，其两个子节点为红色，叔节点不用改变)],如下图所示，注意省略黑哨兵节点
以上就是红黑树新增节点所有可能的操作，下面会介绍红黑树中的删除操作
删除操作
删除操作相比于插入操作情况更加复杂，删除一个节点可以大致分为三种情况：
在讲述修复操作之前，首先需要明白几点，
1.对于红黑树而言，单支节点的情况只有如下图所示的一种情况，即为当前节点为黑色，其孩子节点为红色,(1.假设当前节点为红色，其两个孩子节点必须为黑色，2.若有孙子节点，则必为黑色，导致黑子数量不等，而红黑树不平衡)
2.由于红黑树是特殊的二叉查找树，它的删除和二叉查找树类型，真正的删除点即为删除点A的中序遍历的后继(前继也可以)，通过红黑树的特性可知这个后继必然最多只能有一个孩子，其这个孩子节点必然是右孩子节点，从而为单支情况(即这个后继节点只能有一个红色孩子或没有孩子)
下面将详细介绍，在执行删除节点操作之后，将通过修复操作使得红黑树达到平衡的情况。
- Case 1:被删除的节点为红色，则这节点必定为叶子节点(首先这里的被删除的节点指的是真正删除的节点，通过上文得知的真正删除的节点要么是节点本身，要么是其后继节点，若是节点本身则必须为叶子节点，不为叶子节点的话其会有左右孩子，则真正删除的是其右孩子树上的最小值，若是后继节点，也必须为叶子节点，若不是则其也会有左右孩子，从而和2中相违背)，这种情况下删除红色叶节点就可以了，不用进行其他的操作了。
- Case 2:被删除的节点是黑色，其子节点是红色，将其子节点顶替上来并改变其颜色为黑色，如下图所示
从图中可以看出，操作之后红黑树并未达到平衡状态，而是变成的黑兄的情况
- 黑父二黑侄：将父节点变成新节点的颜色，新节点变成黑色，兄弟节点染成红色，还需要继续以父节点为判定点继续判断,如下图所示
情况一:新节点在右子树，红侄在兄弟节点左子树，此时的操作为右旋，并将兄弟节点变为父亲的颜色，父亲节点变为黑色，侄节点变为黑色，如下图所示
情况二:新节点在右子树，红侄在兄弟节点右子树，此时的操作为先左旋，后右旋并将侄节点变为父亲的颜色，父节点变为黑色，如下图所示
情况三：新节点在左子树，红侄在兄弟节点左子树,此时的操作为先右旋在左旋并将侄节点变为父亲的颜色，父亲节点变为黑色，如下图所示
情况四：新节点在右子树，红侄在兄弟节点右子树,此时的操作为左旋，并将兄弟节点变为父节点的颜色，父亲节点变为黑色，侄节点变为黑色，如下图所示
红黑树实现
如下是使用JAVA代码实现红黑树的过程，主要包括了插入、删除、左旋、右旋、遍历等操作
插入
/* 插入一个节点
* @param node
*/
private void insert(RBTreeNode node){
int cmp;
RBTreeNode root = this.rootNode;
RBTreeNode parent = null;
//定位节点添加到哪个父节点下
while(null != root){
parent = root;
cmp = node.key.compareTo(root.key);
if (cmp < 0){
root = root.left;
} else {
root = root.right;
}
}
node.parent = parent;
//表示当前没一个节点，那么就当新增的节点为根节点
if (null == parent){
this.rootNode = node;
} else {
//找出在当前父节点下新增节点的位置
cmp = node.key.compareTo(parent.key);
if (cmp < 0){
parent.left = node;
} else {
parent.right = node;
}
}
//设置插入节点的颜色为红色
node.color = COLOR_RED;
//修正为红黑树
insertFixUp(node);
}
/**
* 红黑树插入修正
* @param node
*/
private void insertFixUp(RBTreeNode node){
RBTreeNode parent,gparent;
//节点的父节点存在并且为红色
while( ((parent = getParent(node)) != null) && isRed(parent)){
gparent = getParent(parent);
//如果其祖父节点是空怎么处理
// 若父节点是祖父节点的左孩子
if(parent == gparent.left){
RBTreeNode uncle = gparent.right;
if ((null != uncle) && isRed(uncle)){
setColorBlack(uncle);
setColorBlack(parent);
setColorRed(gparent);
node = gparent;
continue;
}
if (parent.right == node){
RBTreeNode tmp;
leftRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
setColorBlack(parent);
setColorRed(gparent);
rightRotate(gparent);
} else {
RBTreeNode uncle = gparent.left;
if ((null != uncle) && isRed(uncle)){
setColorBlack(uncle);
setColorBlack(parent);
setColorRed(gparent);
node = gparent;
continue;
}
if (parent.left == node){
RBTreeNode tmp;
rightRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
setColorBlack(parent);
setColorRed(gparent);
leftRotate(gparent);
}
}
setColorBlack(this.rootNode);
}
插入节点的操作主要分为以下几步：
删除节点
如下为删除节点的代码
private void remove(RBTreeNode node){
RBTreeNode child,parent;
boolean color;
//被删除节点左右孩子都不为空的情况
if ((null != node.left) && (null != node.right)){
//获取到被删除节点的后继节点
RBTreeNode replace = node;
replace = replace.right;
while(null != replace.left){
replace = replace.left;
}
//node节点不是根节点
if (null != getParent(node)){
//node是左节点
if (getParent(node).left == node){
getParent(node).left = replace;
} else {
getParent(node).right = replace;
}
} else {
this.rootNode = replace;
}
child = replace.right;
parent = getParent(replace);
color = getColor(replace);
if (parent == node){
parent = replace;
} else {
if (null != child){
setParent(child,parent);
}
parent.left = child;
replace.right = node.right;
setParent(node.right, replace);
}
replace.parent = node.parent;
replace.color = node.color;
replace.left = node.left;
node.left.parent = replace;
if (color == COLOR_BLACK){
removeFixUp(child,parent);
}
node = null;
return;
}
if (null != node.left){
child = node.left;
} else {
child = node.right;
}
parent = node.parent;
color = node.color;
if (null != child){
child.parent = parent;
}
if (null != parent){
if (parent.left == node){
parent.left = child;
} else {
parent.right = child;
}
} else {
this.rootNode = child;
}
if (color == COLOR_BLACK){
removeFixUp(child, parent);
}
node = null;
}
/**
* 删除修复
* @param node
* @param parent
*/
private void removeFixUp(RBTreeNode node, RBTreeNode parent){
RBTreeNode other;
//node不为空且为黑色，并且不为根节点
while ((null == node || isBlack(node)) && (node != this.rootNode) ){
//node是父节点的左孩子
if (node == parent.left){
//获取到其右孩子
other = parent.right;
//node节点的兄弟节点是红色
if (isRed(other)){
setColorBlack(other);
setColorRed(parent);
leftRotate(parent);
other = parent.right;
}
//node节点的兄弟节点是黑色，且兄弟节点的两个孩子节点也是黑色
if ((other.left == null || isBlack(other.left)) &&
(other.right == null || isBlack(other.right))){
setColorRed(other);
node = parent;
parent = getParent(node);
} else {
//node节点的兄弟节点是黑色，且兄弟节点的右孩子是红色
if (null == other.right || isBlack(other.right)){
setColorBlack(other.left);
setColorRed(other);
rightRotate(other);
other = parent.right;
}
//node节点的兄弟节点是黑色，且兄弟节点的右孩子是红色，左孩子是任意颜色
setColor(other, getColor(parent));
setColorBlack(parent);
setColorBlack(other.right);
leftRotate(parent);
node = this.rootNode;
break;
}
} else {
other = parent.left;
if (isRed(other)){
setColorBlack(other);
setColorRed(parent);
rightRotate(parent);
other = parent.left;
}
if ((null == other.left || isBlack(other.left)) &&
(null == other.right || isBlack(other.right))){
setColorRed(other);
node = parent;
parent = getParent(node);
} else {
if (null == other.left || isBlack(other.left)){
setColorBlack(other.right);
setColorRed(other);
leftRotate(other);
other = parent.left;
}
setColor(other,getColor(parent));
setColorBlack(parent);
setColorBlack(other.left);
rightRotate(parent);
node = this.rootNode;
break;
}
}
}
if (node!=null)
setColorBlack(node);
}
删除节点主要分为几种情况去做对应的处理：
- 1.删除节点,按照如下三种情况去删除节点
- 1.真正删除的节点没有子节点
- 2.真正删除的节点有一个子节点
- 3.正在删除的节点有两个子节点
- 2.修复红黑树的特性，如代码中调用removeFixUp方法修复红黑树的特性。
3.总结
以上主要介绍了红黑树的一些特性，包括一些操作详细的解析了里面的过程，写的时间比较长，感觉确实比较难理清楚。后面会持续的理解更深入，若有存在问题的地方，请指正。
参考文章
红黑树(五)之 Java的实现
通过分析 JDK 源代码研究 TreeMap 红黑树算法实现
红黑树
（图解）红黑树的插入和删除
红黑树深入剖析及Java实现
网站栏目：Java集合详解6：这次，从头到尾带你解读Java中的红黑树
URL地址：
http://cdkjz.cn/article/jjpdjo.html
