目录
一、你还记得什么是红黑树吗？
红黑树是一种二叉搜索树，但在每个结点上又增加一个存储位表示颜色，可以是黑或红；由于最长路径不超过最短路径的两倍，因此，红黑树不像AVL树是绝对平衡的，而是相对平衡的；
性质：
1、每个结点颜色，非黑即红；
2、根节点是黑色的；
3、若一个结点时红色的，则他的两个孩子结点是黑色的；（没有两个连续的红色结点）
4、对于每一个结点，从该结点到所有后代叶节点的简单路径上，黑色结点的数目是相同的；
5、每个叶子结点都是黑色的NIL（空结点）；
为什么有这5点性质，就能保证红黑树，最长路径不超过最短路径的两倍？一张图让你明白，如下：
那么假设，一颗红黑树中有N个黑色结点，那么这颗树的结点数量的范围就是N~2N个，路径长度在logN ~ log2N之间；
二、AVL树与红黑树的比较
AVL树和红黑树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log2 N)，AVL树是绝对的平衡，而红黑树不是绝对的平衡，他只保证最长路径不超过最短路径的2倍，所以对比起来，降低了插入和删除的次数；
应用场景：如果是经常需要进行增删改查，更推荐使用红黑树（实际场合运用的最多的也是红黑树）；如果不经常进行增删改查，而是追求极致的查询效率，推荐使用AVL树；
三、模拟实现红黑树
3.1、红黑树的定义
这里的定义和AVL树的定义差不多，唯一有区别的地方是红黑树多了一个颜色的定义，颜色的定义我们可以通过枚举类来实现，如下代码：
public class RBTree {
static class RBTreeNode {
public RBTreeNode left;
public RBTreeNode right;
public RBTreeNode parent;
public int val;
public COLOR color;
public RBTreeNode(int val) {
this.val = val;
//新增结点，默认必须是红色
this.color = COLOR.RED;
}
}
public RBTreeNode root;//根节点
}public enum COLOR {
RED, BLACK
}注意：
每次新增结点必须是红色的，因为如果某一个分支上增加一个黑色结点，根据红黑树的特点，那么其他每一个分支上也必须都增加一个黑色结点，但实际上我需要增加一个结点，而为了满足红黑树特点多增加的这些结点是没有意义的；如果添加一个红色节点，我们只需要通过调整颜色，即可满足要求；不太理解的话可以看看下面这张图：
若新增结点是黑色的，需要继续添加一些无意义的结点满足红黑树要求，如下：
若新增结点是红色的，只需要修改颜色即可，如下：
3.2、插入结点
红黑树的插入结点和二叉搜索树的插入结点的方式是一样的，那么还有的代码对于AVL树来说就是需要调节平衡因子和旋转；对于红黑树来说就需要考虑颜色了，因为若新增结点是红色的，而他的父亲结点也是红色的，此时就违反了红黑树的性质，因此需要对颜色进行调整，具体调整方式，分为以下三种情况：
首先，这里约定：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点；
3.2.1、情况一
cur为红，p为红，g为黑，u存在且为红，如下：
但是这样就够了吗？
肯定是不够的，因为这里没有考虑 g 的父亲结点是什么颜色的，如果他的父亲结点是黑色，那么若只是单纯的将 p 和 u 修改成黑色，是有可能出问题的，如下：
总结一下 ：
对于以上出现的所有情况，将p 和 u 设置成黑色后，可以直接将结点 g 颜色修改成红色；那如果g就是根节点呢？解决办法就是当所有情况处理完后，无论根节点是什么颜色，都手动将他置为黑色；
如果 g 上面的结点是红色的，那么就继续向上调整，此时 g 结点就相当于是cur结点，p 和 u 依次此向上类推即可，如下图：
那么情况一的代码就有啦，如下：
while (parent != null && parent.color == COLOR.RED) {//parent为红色，就是两个红色结点连在一起了
RBTreeNode grandFather = parent.parent;//这个引用一定不为空，因为此时parent一定是红色！
if(parent == grandFather.left) {
RBTreeNode uncle = grandFather.right;
if(uncle != null && uncle.color == COLOR.RED) {
parent.color = COLOR.BLACK;
uncle.color = COLOR.BLACK;
grandFather.color = COLOR.RED;
//继续向上调整
cur = grandFather;
parent = cur.parent;
} else {
//uncle不存在 或者 uncle是黑色的
}
} else {
}
}3.2.2、情况二
cur为红，p为红，g为黑，u不存在/u为黑，处理方式如下：
而这里的右单旋具体讲解在讲解AVL树那一张就写过啦，没看过的小伙伴可以去看一看这篇：http://t.csdn.cn/MNFBp
代码如下：
public class RBTree {
static class RBTreeNode {
public RBTreeNode left;
public RBTreeNode right;
public RBTreeNode parent;
public int val;
public COLOR color;
public RBTreeNode(int val) {
this.val = val;
//新增结点，默认必须是红色
this.color = COLOR.RED;
}
}
public RBTreeNode root;//根节点
public boolean insert(int val) {
RBTreeNode node = new RBTreeNode(val);
if(root == null) {
root = node;
root.color = COLOR.BLACK;//注意第一次插入根节点一定是黑色
return true;
}
RBTreeNode parent = null;
RBTreeNode cur = root;
while(cur != null) {
if(cur.val > val) {
//向左寻找
parent = cur;
cur = cur.left;
} else if(cur.val == val) {
//相等就说明插入失败
return false;
} else {
//向右寻找
parent = cur;
cur = cur.right;
}
}
//cur == null
if(parent.val > val) {
parent.left = node;
} else {
parent.right = node;
}
node.parent = parent;
cur = node;
//红黑树需要调整颜色
while (parent != null && parent.color == COLOR.RED) {//parent为红色，就是两个红色结点连在一起了
RBTreeNode grandFather = parent.parent;//这个引用一定不为空，因为此时parent一定是红色！
if(parent == grandFather.left) {
RBTreeNode uncle = grandFather.right;
if(uncle != null && uncle.color == COLOR.RED) {
parent.color = COLOR.BLACK;
uncle.color = COLOR.BLACK;
grandFather.color = COLOR.RED;
//继续向上调整
cur = grandFather;
parent = cur.parent;
} else {
//uncle不存在 或者 uncle是黑色的
//这里只需要先右旋，然后修改颜色即可
rotateRight(parent);
parent.color = COLOR.BLACK;
grandFather.color = COLOR.RED;
}
} else {
}
}
}
//右单旋
private void rotateRight(RBTreeNode parent) {
RBTreeNode subL = parent.left;
RBTreeNode subLR = subL.right;
parent.left = subLR;
subL.right = parent;
if(subLR != null) {
subLR.parent = parent;
}
//必须先记录parent的父亲
RBTreeNode pParent = parent.parent;
parent.parent = subL;
//检查parent是否是根节点
if(parent == root) {
root = subL;
root = null;
} else {
//不是根节点，判断parent是左子树还是右子树
if(pParent.left == parent) {
pParent.left = subL;
} else {
pParent.right = subL;
}
subL.parent = pParent;
}
}
3.2.3、情况三
cur为红，p为红，g为黑，u不存在/u为黑，如下：
仔细观察，这不就是 情况二修改完颜色后的样子吗？唯一的差别只是cur和p的指向相互调换了， 所以，这里只需要旋转后调整一下指向即可~
如下代码：
//红黑树需要调整颜色
while (parent != null && parent.color == COLOR.RED) {//parent为红色，就是两个红色结点连在一起了
RBTreeNode grandFather = parent.parent;//这个引用一定不为空，因为此时parent一定是红色！
if(parent == grandFather.left) {
RBTreeNode uncle = grandFather.right;
if(uncle != null && uncle.color == COLOR.RED) {
parent.color = COLOR.BLACK;
uncle.color = COLOR.BLACK;
grandFather.color = COLOR.RED;
//继续向上调整
cur = grandFather;
parent = cur.parent;
} else {
//uncle不存在 或者 uncle是黑色的
//情况三：(这里只需要把情况三处理成情况二)
if(cur == parent.right) {
rotateLeft(parent);
//这里只需要交换一下cur和parent
RBTreeNode tmp = parent;
parent = cur;
cur = tmp;
}//走完这里，情况三就变成了情况二
//情况二：
//这里只需要先右旋，然后修改颜色即可
rotateRight(parent);
parent.color = COLOR.BLACK;
grandFather.color = COLOR.RED;
}
} else {
}
}以上所讲，都是处理grandFarther.left，接下来就需要处理最后一个else的情况grandFarcher.right，实际上和grandFarther.left几乎一样，需要处理的地方就是原本是右旋和左旋需要颠倒一下，以及parent的指向；
如下代码：
public class RBTree {
static class RBTreeNode {
public RBTreeNode left;
public RBTreeNode right;
public RBTreeNode parent;
public int val;
public COLOR color;
public RBTreeNode(int val) {
this.val = val;
//新增结点，默认必须是红色
this.color = COLOR.RED;
}
}
public RBTreeNode root;//根节点
public boolean insert(int val) {
RBTreeNode node = new RBTreeNode(val);
if(root == null) {
root = node;
root.color = COLOR.BLACK;//注意第一次插入根节点一定是黑色
return true;
}
RBTreeNode parent = null;
RBTreeNode cur = root;
while(cur != null) {
if(cur.val > val) {
//向左寻找
parent = cur;
cur = cur.left;
} else if(cur.val == val) {
//相等就说明插入失败
return false;
} else {
//向右寻找
parent = cur;
cur = cur.right;
}
}
//cur == null
if(parent.val > val) {
parent.left = node;
} else {
parent.right = node;
}
node.parent = parent;
cur = node;
//红黑树需要调整颜色
while (parent != null && parent.color == COLOR.RED) {//parent为红色，就是两个红色结点连在一起了
RBTreeNode grandFather = parent.parent;//这个引用一定不为空，因为此时parent一定是红色！
if(parent == grandFather.left) {
RBTreeNode uncle = grandFather.right;
if(uncle != null && uncle.color == COLOR.RED) {
parent.color = COLOR.BLACK;
uncle.color = COLOR.BLACK;
grandFather.color = COLOR.RED;
//继续向上调整
cur = grandFather;
parent = cur.parent;
} else {
//uncle不存在 或者 uncle是黑色的
//情况三：(这里只需要把情况三处理成情况二)
if(cur == parent.right) {
rotateLeft(parent);
//这里只需要交换一下cur和parent
RBTreeNode tmp = parent;
parent = cur;
cur = tmp;
}//走完这里，情况三就变成了情况二
//情况二：
//这里只需要先右旋，然后修改颜色即可
rotateRight(parent);
parent.color = COLOR.BLACK;
grandFather.color = COLOR.RED;
}
} else {
//parent == grandFather.right
RBTreeNode uncle = grandFather.left;
if(uncle != null && uncle.color == COLOR.RED) {
parent.color = COLOR.BLACK;
uncle.color = COLOR.BLACK;
grandFather.color = COLOR.RED;
//继续向上调整
cur = grandFather;
parent = cur.parent;
} else {
//uncle不存在 或者 uncle是黑色的
//情况三：(这里只需要把情况三处理成情况二)
if(cur == parent.left) {
rotateRight(parent);
//这里只需要交换一下cur和parent
RBTreeNode tmp = parent;
parent = cur;
cur = tmp;
}//走完这里，情况三就变成了情况二
//情况二：
//这里只需要先右旋，然后修改颜色即可
rotateLeft(parent);
parent.color = COLOR.BLACK;
grandFather.color = COLOR.RED;
}
}
}
root.color = COLOR.BLACK;
return true;
}
//左单旋
private void rotateLeft(RBTreeNode parent) {
RBTreeNode subR = parent.right;
RBTreeNode subRL = subR.left;
parent.right = subRL;
subR.left = parent;
if(subRL != null) {
subRL.parent = parent;
}
//必须先记录parent的父亲
RBTreeNode pParent = parent.parent;
parent.parent = subR;
//检查parent是否为根节点
if(parent == root) {
root = subR;
root.parent = null;
} else {
//不是根节点需要判断parent是左子树还是右子树
if(pParent.left == parent) {
pParent.left = subR;
} else {
pParent.right = subR;
}
subR.parent = pParent;
}
}
//右单旋
private void rotateRight(RBTreeNode parent) {
RBTreeNode subL = parent.left;
RBTreeNode subLR = subL.right;
parent.left = subLR;
subL.right = parent;
if(subLR != null) {
subLR.parent = parent;
}
//必须先记录parent的父亲
RBTreeNode pParent = parent.parent;
parent.parent = subL;
//检查parent是否是根节点
if(parent == root) {
root = subL;
root = null;
} else {
//不是根节点，判断parent是左子树还是右子树
if(pParent.left == parent) {
pParent.left = subL;
} else {
pParent.right = subL;
}
subL.parent = pParent;
}
}
}芜湖~这样整个插入就完成了~
四、红黑树的验证
验证是否为红黑树就是要看是否满足红黑树的特性；
4.1、检查中序遍历是否有序
这个就是简单的中序遍历~
代码如下：
public void dfs(RBTreeNode root) {
if(root == null) {
return;
}
dfs(root.left);
System.out.print(root.val + " ");
dfs(root.right);
}3.2、检查是否出现两个连续的红色结点
这里可以反向去检查，也就是说，当你遍历到一个红色结点时，只需要看一下他的父亲结点是否是黑色，若是黑色的就满足要求，若不是，就不是红黑树；
代码如下：
//检查是否出现俩个连续的红色结点
private boolean checkRedColor(RBTreeNode root) {
if(root == null) {
return true;
}
if(root.color == COLOR.RED) {
RBTreeNode parent = root.parent;
if(parent.color == COLOR.RED) {
System.out.println("不是红黑树，违反了性质：不可以出现两个连续的红色结点");
return false;
}
}
return checkRedColor(root.left) && checkRedColor(root.right);
4.3、检查每条路径的黑色结点数目是否相同
可以通过递归遍历每一个结点，创建一个计数器，一旦遍历到黑色结点计数器就加一，若当前结点的左右子树都为空，说明一条路径已经遍历完了，这个适合就可以对比黑色结点数目相同，满足要求；
代码如下：
/**
*
* @param root
* @param pathBlackNum 递归时每条路径上的黑色结点个数
* @param BlackNum 以及计算好的黑色结点个数
* @return
*/
private boolean checkBlackNum(RBTreeNode root, int pathBlackNum, int BlackNum) {
if(root == null) {
return true;
}
if(root.color == COLOR.BLACK) {
pathBlackNum++;
}
if(root.left == null && root.right == null) {
if(pathBlackNum != BlackNum) {
System.out.println("不是红黑树，违反了性质：每条路径上的黑色结点个数相同");
return false;
}
}
return checkBlackNum(root.left, pathBlackNum, BlackNum) &&
checkBlackNum(root.left, pathBlackNum, BlackNum);
}4.4、验证红黑树是否满足要求（综合）
这里除了要综合以上的检查方法，同时还要判断根节点的颜色，若根节点的颜色不是黑色，则说明不满足要求；
代码如下：
//验证红黑树(就是要满足红黑树的性质)
public boolean isRBTree(RBTreeNode root) {
if(root == null) {
return true;
}
if (root.color != COLOR.BLACK) {
System.out.println("不是红黑树，违反了性质：根节点是黑色的");
}
int BlackNum = 0;
RBTreeNode cur = root;
while(root != null) {
if(root.color == COLOR.BLACK) {
BlackNum++;
}
root = root.left;
}
// 检查是否出现俩个连续的红色结点 && 检查每条路径黑色结点数是否相同
return checkRedColor(root) && checkBlackNum(root, 0, BlackNum);
五、完整红黑树代码
public class RBTree {
static class RBTreeNode {
public RBTreeNode left;
public RBTreeNode right;
public RBTreeNode parent;
public int val;
public COLOR color;
public RBTreeNode(int val) {
this.val = val;
//新增结点，默认必须是红色
this.color = COLOR.RED;
}
}
public RBTreeNode root;//根节点
public boolean insert(int val) {
RBTreeNode node = new RBTreeNode(val);
if(root == null) {
root = node;
root.color = COLOR.BLACK;//注意第一次插入根节点一定是黑色
return true;
}
RBTreeNode parent = null;
RBTreeNode cur = root;
while(cur != null) {
if(cur.val > val) {
//向左寻找
parent = cur;
cur = cur.left;
} else if(cur.val == val) {
//相等就说明插入失败
return false;
} else {
//向右寻找
parent = cur;
cur = cur.right;
}
}
//cur == null
if(parent.val > val) {
parent.left = node;
} else {
parent.right = node;
}
node.parent = parent;
cur = node;
//红黑树需要调整颜色
while (parent != null && parent.color == COLOR.RED) {//parent为红色，就是两个红色结点连在一起了
RBTreeNode grandFather = parent.parent;//这个引用一定不为空，因为此时parent一定是红色！
if(parent == grandFather.left) {
RBTreeNode uncle = grandFather.right;
if(uncle != null && uncle.color == COLOR.RED) {
parent.color = COLOR.BLACK;
uncle.color = COLOR.BLACK;
grandFather.color = COLOR.RED;
//继续向上调整
cur = grandFather;
parent = cur.parent;
} else {
//uncle不存在 或者 uncle是黑色的
//情况三：(这里只需要把情况三处理成情况二)
if(cur == parent.right) {
rotateLeft(parent);
//这里只需要交换一下cur和parent
RBTreeNode tmp = parent;
parent = cur;
cur = tmp;
}//走完这里，情况三就变成了情况二
//情况二：
//这里只需要先右旋，然后修改颜色即可
rotateRight(parent);
parent.color = COLOR.BLACK;
grandFather.color = COLOR.RED;
}
} else {
//parent == grandFather.right
RBTreeNode uncle = grandFather.left;
if(uncle != null && uncle.color == COLOR.RED) {
parent.color = COLOR.BLACK;
uncle.color = COLOR.BLACK;
grandFather.color = COLOR.RED;
//继续向上调整
cur = grandFather;
parent = cur.parent;
} else {
//uncle不存在 或者 uncle是黑色的
//情况三：(这里只需要把情况三处理成情况二)
if(cur == parent.left) {
rotateRight(parent);
//这里只需要交换一下cur和parent
RBTreeNode tmp = parent;
parent = cur;
cur = tmp;
}//走完这里，情况三就变成了情况二
//情况二：
//这里只需要先右旋，然后修改颜色即可
rotateLeft(parent);
parent.color = COLOR.BLACK;
grandFather.color = COLOR.RED;
}
}
}
root.color = COLOR.BLACK;
return true;
}
//左单旋
private void rotateLeft(RBTreeNode parent) {
RBTreeNode subR = parent.right;
RBTreeNode subRL = subR.left;
parent.right = subRL;
subR.left = parent;
if(subRL != null) {
subRL.parent = parent;
}
//必须先记录parent的父亲
RBTreeNode pParent = parent.parent;
parent.parent = subR;
//检查parent是否为根节点
if(parent == root) {
root = subR;
root.parent = null;
} else {
//不是根节点需要判断parent是左子树还是右子树
if(pParent.left == parent) {
pParent.left = subR;
} else {
pParent.right = subR;
}
subR.parent = pParent;
}
}
//右单旋
private void rotateRight(RBTreeNode parent) {
RBTreeNode subL = parent.left;
RBTreeNode subLR = subL.right;
parent.left = subLR;
subL.right = parent;
if(subLR != null) {
subLR.parent = parent;
}
//必须先记录parent的父亲
RBTreeNode pParent = parent.parent;
parent.parent = subL;
//检查parent是否是根节点
if(parent == root) {
root = subL;
root = null;
} else {
//不是根节点，判断parent是左子树还是右子树
if(pParent.left == parent) {
pParent.left = subL;
} else {
pParent.right = subL;
}
subL.parent = pParent;
}
}
//验证红黑树(就是要满足红黑树的性质)
public boolean isRBTree(RBTreeNode root) {
if(root == null) {
return true;
}
if (root.color != COLOR.BLACK) {
System.out.println("不是红黑树，违反了性质：根节点是黑色的");
}
int BlackNum = 0;
RBTreeNode cur = root;
while(root != null) {
if(root.color == COLOR.BLACK) {
BlackNum++;
}
root = root.left;
}
// 检查是否出现俩个连续的红色结点 && 检查每条路径黑色结点数是否相同
return checkRedColor(root) && checkBlackNum(root, 0, BlackNum);
}
/**
*
* @param root
* @param pathBlackNum 递归时每条路径上的黑色结点个数
* @param BlackNum 以及计算好的黑色结点个数
* @return
*/
private boolean checkBlackNum(RBTreeNode root, int pathBlackNum, int BlackNum) {
if(root == null) {
return true;
}
if(root.color == COLOR.BLACK) {
pathBlackNum++;
}
if(root.left == null && root.right == null) {
if(pathBlackNum != BlackNum) {
System.out.println("不是红黑树，违反了性质：每条路径上的黑色结点个数相同");
return false;
}
}
return checkBlackNum(root.left, pathBlackNum, BlackNum) &&
checkBlackNum(root.left, pathBlackNum, BlackNum);
}
//检查是否出现俩个连续的红色结点
private boolean checkRedColor(RBTreeNode root) {
if(root == null) {
return true;
}
if(root.color == COLOR.RED) {
RBTreeNode parent = root.parent;
if(parent.color == COLOR.RED) {
System.out.println("不是红黑树，违反了性质：不可以出现两个连续的红色结点");
return false;
}
}
return checkRedColor(root.left) && checkRedColor(root.right);
}
//检查中序遍历是否有序
public void dfs(RBTreeNode root) {
if(root == null) {
return;
}
dfs(root.left);
System.out.print(root.val + " ");
dfs(root.right);
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/129827.html
